159. Longest Substring with At Most Two Distinct Characters ----M

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

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

A:

****************第一遍*****************************
记录了两个char 来计算。 这里tricky的一点就是，如果新加入了第三个char , 在 i 位置，那么i-1

位置就是 另外一个char。  倒退回去就知道最新长度了

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int n = s.length();
        if(n<=2)
            return n;
        // sliding window        
        int pre = -1;
        char c1 = s[0], c2 = c1;
        int res = 0;
        for(int i = 0;i<s.length();i++){
            char ch = s[i];
            if(ch != c1 && ch != c2){
                c2 = ch;
                c1 = s[i-1];
                pre = i-2;
                while(pre>=0 && s[pre]==c1){
                    --pre;
                }
            }
            res = max(res, i - pre);
        }
        return res;
    }
};

*******用Map  来计数****************

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int res = 0, pre = -1;
        Map<Character,Integer> map = new HashMap();
        for(int i =0;i< s.length(); i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                map.put(ch,1+map.get(ch));
            }else{
                while(map.size() >= 2){
                    char tmp = s.charAt(++pre);
                    map.put(tmp,map.get(tmp)-1);
                    if(map.get(tmp)==0)
                        map.remove(tmp);
                }
                map.put(ch,1);
            }
            res = Math.max(res, i-pre);
        }
        return res;
    }
}