问题
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;
}
};
