【LeetCode】3.最长不重复子串

问题

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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

最长不重复字串问题：给定一个字符串，找出字符串中的最长不重复字串，返回其字符串长度。

分析

首先想到的是O(N^2)方法，针对可能的每个字符子串进行查找，计算长度。

保持一个字符串左边界，右边界不断移动，判断当前字符串[left, right]是否是不重复字串。如果是，计算长度；如果不是，更换左边界。

左边界更换的触发条件是当前字符s[right]，在字符串s[left, right-1]中出现了；否则，即没有出现在子串当中，计算当前字符串长度。

• 如果出现在子串中，更换左边界：左边界换为当前字符在数据中存储位置的下一位；
• 如果没出现在字串中，此时有两种情况：确实没出现；出现位置不在子串窗口范围内，即位置<left

为了方便，这里使用一个字典存储字符与下一次重复时左边界的移动位置。

还有一个问题是子串长度什么时候计算的问题。是字符发生重复时，还是没有重复字符？

如果是有字符重复时计算，那么有一种情况为整个子串都没有重复字符，此时，一直不会触发长度计算；所以，理想情况是没有发生字符重复时||重复字符不在窗口范围内，此时计算子串长度。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        int result = 0, left = 0, right = 0;
        //unordered_map<char, int> dict;
        vector<int> dict(256, 0);//字符做下标
        
        while (right < s.size()){
            if (dict[s[right]] == 0 || dict[s[right]] < left)
                result = max(right - left + 1, result);
            else
                left = dict[s[right]];
            
            dict[s[right]] = right + 1;
            right++;
            
        }
        
        return result;
    }
};