340. Longest Substring with At Most K Distinct Characters - jiejackyzhang/leetcode-note GitHub Wiki

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

For example, Given s = “eceba” and k = 2,

T is "ece" which its length is 3.

思路: 一个hash表和一个左边界标记. 遍历字符串将其加入到hash表中, 不同字符多于k个了, 就从左边开始删字符. 直到hash表不同字符长度等于k.此时字符串的长度就是当前字符和左边界的距离.

public int lengthOfLongestSubstringKDistinct(String s, int k) {  
    int len = 0, n = s.length();  
    int left = 0;  
    Map<Character, Integer> map = new HashMap<>();  
    for(int i=0; i<n; i++) {  
        char c = s.charAt(i);  
        Integer cnt = map.get(c);  
        if(cnt == null) cnt = 0;  
        map.put(c, cnt+1);  
        while(map.size() > k) {  
            char key = s.charAt(left++);  
            int val = map.get(key)-1;  
            if(val == 0) {  
                map.remove(key);  
            } else {  
                map.put(key, val);  
            }  
        }  
        len = Math.max(len, i-left+1);  
    }   
    return len;
}