leetcode 159: Longest Substring with At Most Two Distinct Characters

1465 ワード

Total Accepted: 1167 Total Submissions: 3961
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.
[解析]
現在の2文字の数をHASHTABLEで記録する、新しい文字に遭遇した場合、startポインタの位置を新しいstart位置まで移動し、2文字のみを含む.この問題は考え方が簡単で、なぜかHARDと表記されている.もっと良い解があるかもしれませんが、extra spaceを使う必要はありません.
[code]
public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        //input check
        if(s== null || s.length()==0) return 0;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int start = 0;
        int max = 0;
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(map.containsKey(c)) {
                map.put( c,   map.get(c) + 1 );
            } else if(map.size() < 2) {
                map.put(c, 1);
            } else {
                while( (map.size()==2) && start<i) {
                    char temp = s.charAt(start);
                    int x = map.get(temp);
                    --x;
                    if(x==0) map.remove(s.charAt(start));
                    else map.put(s.charAt(start), x);
                    ++start;
                }
                map.put(c,1);
            }
            max = Math.max(max, i-start+1);
        }
        return max;
    }
}