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.
我的做法：维护一个window，r移动到超出k distinct character限制是更新max，然后移动l使distinct character <=k; 这种做法更新max只发生在超出限制的时候，有可能永远都没有超出限制，所以while loop完了之后要补上一个max的更新
public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int l=0, r=0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int longest = 0;
if (s==null || s.length()==0 || k<=0) return longest;
while (r < s.length()) {
char cur = s.charAt(r);
map.put(cur, map.getOrDefault(cur, 0) + 1);
if (map.size() > k) {
longest = Math.max(longest, r-l);
while (map.size() > k) {
char rmv = s.charAt(l);
if (map.get(rmv) == 1) map.remove(rmv);
else map.put(rmv, map.get(rmv)-1);
l++;
}
}
r++;
}
longest = Math.max(longest, r-l);
return longest;
}
}
别人非常棒的做法：sliding window，while loop里面每次循环都会尝试更新max，所以每次更新之前都是把l, r调整到合适的位置，也就是说，一旦r移动到超出K distinct char限制，l也要更新使k distinct char重新满足，l更新是在max更新之前
public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int[] count = new int[256];
int num = 0, i = 0, res = 0; //num is # of distinct char, i is left edge, j is right edge
for (int j = 0; j < s.length(); j++) {
if (count[s.charAt(j)]++ == 0) num++;
if (num > k) {
while (--count[s.charAt(i++)] > 0);
num--;
}
res = Math.max(res, j - i + 1);
}
return res;
}
}