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

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

T is "ece" which its length is 3.

159. Longest Substring with At Most Two Distinct Characters 的拓展，159题是最多有2个不同字符，这里是最多有k个不同字符。

解题方法一样，只是把比较不同字符个数时的2换成k。

Java：

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
    	if (s == null || s.length() == 0 || k <= 0) {
    		return 0;
    	}
    	HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    	int count = 0;
    	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 {
    			map.put(c, 1);
    			while (map.size() > k) {
	    			char rm = s.charAt(start);
	    			int tempCount = map.get(rm);
	    			if (tempCount > 1) {
	    				map.put(rm, tempCount - 1);
	    			} else {
	    				map.remove(rm);
	    			}
	    			start++;
	    			count--;
	    		}
    		}
    		count++;
    		max = Math.max(max, count);
    	}
    	return max;
    }
}

Python：

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        longest, start, distinct_count, visited = 0, 0, 0, [0 for _ in xrange(256)]
        for i, char in enumerate(s):
            if visited[ord(char)] == 0:
                distinct_count += 1
            visited[ord(char)] += 1
            
            while distinct_count > k:
                visited[ord(s[start])] -= 1
                if visited[ord(s[start])] == 0:
                    distinct_count -= 1
                start += 1
  
            longest = max(longest, i - start + 1)
        return longest

类似题目：

[LeetCode] 3.Longest Substring Without Repeating Characters 最长无重复子串

[LeetCode] 159. Longest Substring with At Most Two Distinct Characters 最多有两个不同字符的最长子串

All LeetCode Questions List 题目汇总