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.
一刷
解法同159侧但， 就是用一個(gè)map存character, index. 保證map的size小于k, 否則，尋找map中entry擁有最小的value旋恼。但是有更快的方法泊交，比如有序的map. 留給二刷
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if(k == 0 || s == null || s.length()==0) return 0;
int res = 0;
Map<Character, Integer> map = new HashMap<>();
int left = 0, right = 0;
for(int i=0; i<s.length(); i++){
char ch = s.charAt(i);
if(map.size()<k || map.containsKey(ch)){
map.put(ch, i);
res = Math.max(res, i-left+1);
}else{
//find the minimum in the map
int value = Integer.MAX_VALUE;
char key = 'a';
for(Map.Entry<Character, Integer> entry : map.entrySet()){
if(entry.getValue()<value) {
value = entry.getValue();
key = entry.getKey();
}
}
map.remove(key);
map.put(ch, i);
left = value+1;
res = Math.max(res, i-left+1);
}
}
return res;
}
}
二刷
詞頻統(tǒng)計(jì)array, sliding window
如果是該char第一次出現(xiàn)疑务，count++
如果count>k, 那么從start開(kāi)始remove, 如果remove后，詞頻數(shù)組顯示這個(gè)ch沒(méi)有出現(xiàn)，那么count--, 直到count==k
class Solution {
// Solution 1: two pointer
// Solution 2: TreeMap<>. dealing with stream input
public int lengthOfLongestSubstringKDistinct(String s, int k) {
char[] arr = s.toCharArray();
int[] table = new int[256];
int start = 0;
int maxLen = 0;
int count = 0;
for(int end = 0; end < arr.length; end++) {
if(table[arr[end]]++ == 0) {
count++;
while(count > k) {
if(--table[arr[start++]] == 0) {
count--;
}
}
}
maxLen = Math.max(maxLen, end - start + 1);
}
return maxLen;
}
}
