无重复字符的最长子串

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

其他滑动窗口题目:

3. 无重复字符的最长子串

209. 长度最小的子数组

30. 串联所有单词的子串

76. 最小覆盖子串

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

LCR 014. 字符串的排列

632. 最小区间

最小窗口子序列

至多包含两个不同字符的最长子串

解题思路

使用map记录每个字母出现的最新的下标

1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

2、如果当前字符 ch 包含在 map中，此时有2类情况：
1）当前字符包含在当前最长有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca，同时把新加入的a下标放进map，因为left已经更新了，所以此时i - left + 1的字符串都是未重复的。
2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b；

​ 随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，那么子段变成bba，这是错误的。实际上，left此时应该不变，left始终为2，子段变成 ba才对。

​ 为了处理以上2类情况，我们每次更新left，**left=Math.max(left , map.get(ch)+1)**，因为要保证left到i之间不存在重复的元素。另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！

map记录最后出现的下标

class Solution {
    public int lechngthOfLongestSubstring(String s) {
        if(s.length() == 0) return 0;
        Map<Character, Integer> map = new HashMap<>(); //记录每个字母出现的最新下标
        int max_len  = 0;
        int left = 0;//左指针
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                //left更新，保持[left,i]中不存在重复的元素
                //1, 字符包含在当前最长字段中，如abca，当前最长子段abc,left = map.get(a)+1 = 1
                //2, 字符不包含在当前最长字段中，如abba，当前最长子段为b,left = left = 2
                left = Math.max(left, map.get(c) + 1);
            }
            //不管是否更新left，都要更新 s.charAt(i) 的位置！
            map.put(c, i);
            max_len = Math.max(max_len, i - left + 1); //左指针与下标之间的长度和max_len比较
            
        }
        return max_len;
    }
}

Set记录当前字串出现的字符

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0)
            return 0;
        int left = 0;
        int right = 0;
        int max = 0;
        Set<Character> set = new HashSet<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            if (!set.contains(c)) {
                set.add(c);
                max = Math.max(max, right - left + 1);
            } else {
                while (set.contains(c)) {
                    char l = s.charAt(left);
                    set.remove(l);
                    left++;
                }
                set.add(c);
            }
            right++;
        }
        return max;

    }
}