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

原题地址：https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/

题解

滑动窗口

设left和right分别为窗口的两端指针，且窗口内元素永远为符合条件的元素

基本思路：

维护一个map，记录窗口中每个字符的数量，right不断向右扩展，并维护map，当map[s.charAt(right)]自加完等于1，则说明此字符是一个新字符，用flag记录下当前窗口内字符种类数，当下一个字符的map为0且flag为2时则跳出循环，此时[left,right]为固定当前left指针下的最长窗口

此时更新left使窗口收缩，每次map[s.charAt(left)]–然后left++来删除最左端字符，当删除到某个字符的map为0时说明成功删除窗口中的一种字符，由于此时的right指针已经在map自加过一次，更新完left后需要让right再++一次来跳过

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int left=0,right=0,max=Integer.MIN_VALUE;
        int[] map=new int[128];
        int flag=0;
        while (left<s.length()){
            while (right<s.length()){
                map[s.charAt(right)]++;
                //当前字符为新字符则flag++
                if(map[s.charAt(right)]==1){
                    if(flag<2)flag++;
                }
                //下一个字符为新字符则跳出
                if(right==s.length()-1||(flag==2&&map[s.charAt(right+1)]==0)){
                    break;
                }
                right++;
            }
            max=Math.max(max,right-left+1);
            while (left<right){
                map[s.charAt(left)]--;
                left++;
                //减少一种字符则跳出
                if(map[s.charAt(left-1)]==0)break;
            }
            right++;
        }
        return max;
    }
}