給定一個(gè)字符串 s ，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
示例 1:

輸入: s = "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。

示例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

示例 4:

輸入: s = ""
輸出: 0

提示：

0 <= s.length <= 5 * 104
s 由英文字母、數(shù)字、符號(hào)和空格組成

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

1、滑動(dòng)窗口

考慮使用滑動(dòng)窗口，需要兩個(gè)指針截取子串，判斷子串是否包含重復(fù)字符，若不包含重復(fù)字符，則將右指針右移，若右指針右移后指向的字符在子串中已經(jīng)存在，則將左指針右移直到子串中再無重復(fù)字符。每次移動(dòng)指針都需要判斷是否存在重復(fù)字符，使用哈希集合進(jìn)行判斷。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int length = s.length();
        int maxLength = 0;
        int left = 0;
        int right = 0;
        while(left < length && right < length){
            if(set.contains(s.charAt(right))){
                int curLength = set.size();
                set = new HashSet<>();
                maxLength = Math.max(curLength, maxLength);
                while(s.charAt(left) != s.charAt(right)){
                    left++;
                }
                left = right + 1;
            }
            set.add(s.charAt(right++));
        }
        return maxLength;
    }
}

不出意外解答錯(cuò)誤，僅當(dāng)字符串中存在重復(fù)字符時(shí)才進(jìn)行最長(zhǎng)子串的計(jì)算，則字符串中無重復(fù)字符時(shí)結(jié)果便為0。首先可以確定的是，右指針每次都會(huì)右移，則可改用for循環(huán)不停移動(dòng)右指針，當(dāng)遇到重復(fù)字符時(shí)，移動(dòng)左指針，同時(shí)將對(duì)應(yīng)字符從哈希集合中刪除，則在哈希集合中便可始終維護(hù)當(dāng)前的無重復(fù)字符子串。

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