159. Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

一刷
题解：
用map存character->index, 如果map满了（多于2个），则选出map中index最小的，剔除。并保存two pointer, 指向subarray（不多于2个distinct character）的首尾两端

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s.length()<1) return 0;
        HashMap<Character, Integer> index = new HashMap<>();
        int lo = 0, hi = 0, maxLength = 0;
        while(hi<s.length()){
            if(index.size()<=2){
                char c = s.charAt(hi);
                index.put(c, hi);
                hi++;
            }
            if(index.size()>2){//remove the leftmost
                int leftMost = s.length();
                for(int i : index.values()){
                    leftMost = Math.min(leftMost, i);
                }
                char c = s.charAt(leftMost);
                index.remove(c);
                lo = leftMost+1;
            }
            maxLength = Math.max(maxLength, hi-lo);
        }
        return maxLength;
    }
}

二刷
思路同上。不过如果是多个distinct character，可以用treemap， 那么可以直接取到index最小的character然后除去

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int start = 0, max = 0;
        for(int i=0; i<s.length(); i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch) || map.size()<=1) map.put(ch, i);
            else{
                int min = Integer.MAX_VALUE;
                for(int cur : map.values()){
                    min = Math.min(cur, min);
                }
                map.remove(s.charAt(min));
                map.put(ch, i);
                start = min+1;
            }
            max = Math.max(i-start+1, max);
        }
        return max;
    }
}