[Amazon] Longest Substring with At Most K Distinct Characters

O(n), n is the size of the string s.

思路：right指针遍历先统计到第一个使map.size()>k的字符，这时候，left指针从头开始遍历，直到可以使map.size()=k

           最长的位置就是left到right，因此最长的个数就是right-left+1

public class Solution {
    /**
     * @param s : A string
     * @return : The length of the longest substring 
     *           that contains at most k distinct characters.
     */
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character,Integer> map=new HashMap<>();
        int longest=0;
        int left=0;
        for(int right=0;right<s.length();right++){
            char ch=s.charAt(right);
            if(!map.containsKey(ch)){
                map.put(ch,1);
            }else{
                map.put(ch,map.get(ch)+1);
            }
            while(map.size()>k){
                char leftChar=s.charAt(left);
                map.put(leftChar,map.get(leftChar)-1);        //遍历left，直到可以使map.size()减少1
                if(map.get(leftChar)==0){                     //也就是说right被统计过的字符
                    map.remove(leftChar);                     //哪个的个数先减小到0，就停止
                }
                left++;
            }
            longest=Math.max(longest,right-left+1);
        }
        
        return  longest;
    }
}