3. Longest Substring Without Repeating Characters (M)

https://leetcode.com/problems/longest-substring-without-repeating-characters/

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

Version 3:

https://www.jiuzhang.com/solution/longest-substring-without-repeating-characters/