Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.
Solution:
Version 1:
这个题终于有了点新意，不是一套框架就出答案，不过反而更简单了，稍微改一改框架就行了：
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window;
int left = 0, right = 0;
int res = 0; // 记录结果
while (right < s.size()) {
char c = s[right];
right++;
// 进行窗口内数据的一系列更新
window[c]++;
// 判断左侧窗口是否要收缩
while (window[c] > 1) {
char d = s[left];
left++;
// 进行窗口内数据的一系列更新
window[d]--;
}
// 在这里更新答案
res = max(res, right - left);
}
return res;
}
JAVA Version:
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0) return 0;
int left = 0,right = 0, result = 0;
HashMap<Character, Integer> map = new HashMap<>();
while(right < s.length())
{
char r = s.charAt(right);
right++;
map.put(r, map.getOrDefault(r,0)+1);
while(map.get(r) > 1)
{
char l = s.charAt(left);
left++;
map.put(l, map.get(l)-1);
}
result = Math.max(result, right-left);
}
return result;
}
}
这就是变简单了，连 need 和 valid 都不需要，而且更新窗口内数据也只需要简单的更新计数器 window 即可。
当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了嘛。
唯一需要注意的是，在哪里更新结果 res 呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？
这里和之前不一样，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。
Version 2:
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int start = 0;
int end = 0;
int result = 0;
HashSet<Character> set = new HashSet<Character>();
while (end < s.length()) {
char current = s.charAt(end);
if (!set.contains(current)) {
set.add(current);
result = Math.max(result, set.size());
}
else{
while (start < s.length() && s.charAt(start) != current ) {
set.remove(s.charAt(start));
start++;
}
start++;
}
end++;
}
result = Math.max(result,set.size());
return result;
}
}