3-无重复的最长字串

力扣3/牛客NC41

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

这道题，这个思路很妙

用一个长度为26的数组记录出现的字符次数，如alph[0] = 1就代表a出现了1次

最大不重复子串可能出现在哪里？用|代表两端，o代表任意字符，x代表重复字符，过程如下：

|ooxoo|x 下一个不为0（alph[r + 1] ！= 0），也就是|内|有重复
o|oxoo|x 左边不断收缩，因为左边统计过，右边不可能更长
oo|xoo|x
oox|oo|x 右边才可以继续前进
oox|oox|…

public int lengthOfLongestSubstring(String s) {
    int[] alph = new int[256];
    int l = 0, r = 0, result = 0;
    while (r < s.length()){
        if (alph[s.charAt(r)] == 0){
            result = Math.max(result, r - l + 1);
            alph[s.charAt(r)]++;
            r++;
        }else {
            alph[s.charAt(l)]--;
            l++;
        }
    }
    return result;
}