3. Longest Substring Without Rep

Description

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

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 subsequence and not a substring.

Solution

• 滑动窗口法
  遍历字符串，维护一个dict记录历史字符出现的位置，同时不断地调整左侧窗口的位置（注意if条件），时间复杂度O(n)，空间O(1)

int lengthOfLongestSubstring(string s) {
    vector<int> dict(256, -1);
    int start = 0, maxLen = 0;
    for (int i=0; i<s.length(); ++i) {
        //历史出现过该字符，且当前窗口包含了该历史字符
        if (dict[s[i]] > -1 && dict[s[i])] >= start) {
            start = dict[s[i]] + 1;
        }
        maxLen = max(maxLen, i - start + 1);
        dict[s[i]] = i;
    }
    return maxLen;
}