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來存放每個字母出現(xiàn)的次數(shù)鸠项。循環(huán)遍歷右指針i, 往hashMap里更新distinct characters. 當(dāng)hashMap的size() > k 的時候止状，我們開始通過start指針從左邊刪字符, 直到hash.size() <= k. 注意這里要先在hashMap里減少字符個數(shù)惧盹，當(dāng)字符個數(shù)還剩1時繼續(xù)減才能刪除栋艳。
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;
}
}
