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.
这道题从最基本的Longest Substring with At Most 2 Distinct Characters开始，基本思路是一样的，这类题必须按照sliding windows的套路解题。一开始维持一个左指针start, 新建一个hashMap来存放每个字母出现的次数。循环遍历右指针i, 往hashMap里更新distinct characters. 当hashMap的size() > k 的时候，我们开始通过start指针从左边删字符, 直到hash.size() <= k. 注意这里要先在hashMap里减少字符个数，当字符个数还剩1时继续减才能删除。
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s == null || s.length() == 0){
return 0;
}
if (s.length() < k){
return s.length();
}
int start = 0;
int maxLen = k;
HashMap<Character, Integer> hash = new HashMap<>();
for (int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if (!hash.containsKey(ch)){
hash.put(ch, 1);
} else {
hash.put(ch, hash.get(ch) + 1);
}
maxLen = Math.max(maxLen, i - start);
while (hash.size() > 2){
char cha = s.charAt(start);
if (hash.get(cha) == 1){
hash.remove(cha);
} else if (hash.get(cha) > 1){
hash.put(cha, hash.get(cha) - 1);
}
start++;
}
}
maxLen = Math.max(maxLen, s.length() - start);
return maxLen;
}
}
