3. Longest Substring Without Repeating Characters

发表于 | 分类于 | |

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.

题意是给你一个字符串，找出里面最长字符不重复的子串（注意不是子序列）。

刷这道题导致停了好几天LeetCode.可能是一开始就被它只有百分之二十几的通过率给吓到了。就觉得超出自己能力了，所以想了一想然后就果断看了大神的代码。但是，悲催的是，看了之后还是很难以理解，尽管代码只有区区9行，其中关键的也就是只有三行。

终于在今天下午看懂了这道题的思路，其实看破了也不会很难，可能自己智商这几天已经不在线了吧。0-0

其实，这道题既然要最长字符不重复的子串，因为子串相对于子序列而言是连续的，所以只遍历一遍，然后把字符串切割为几段字符不重复的子串，然后找一个变量maxLen维护目前最长的就好了。具体如下图：

所以关键就是在于怎么把字符串切割为几段字符不重复的子串了并记录长度了。

用start来表示每个子串的起始位置，然后逐个逐个往前遍历，当发现遍历到的这个字符已经在当前子串存在了，就将start挪到这个位置，重新计算新的子串。

那么，问题又来了，怎么判断这个字符已经出现在当前子串当中了呢？

做法是采用hash的思想，将每个字符都映射到它在字符串的位置，当发现这个遍历到的这个字符的value（也就是它在字符串的index）比start大，那就说明它是存在当前子串当中的。

最后用一个maxLen来维护整个过程中划分的子串的最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        vector<int> dict(256, -1);
        int maxLen = 0, start = -1;
        for (int i = 0; i != s.length(); i++) {
            if (dict[s[i]] > start)
                start = dict[s[i]];
            dict[s[i]] = i;
            maxLen = max(maxLen, i - start);
        }
        return maxLen;
    }
    
};