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.

Sliding Window

这个题目也是substring类型的题目, 博客里有个模板可以参考, 请搜索Substring Problems Template.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s == null || s.length() == 0)
        return 0;
    int[] map = new int[128];
    int start = 0, end = 0;
    int count = 0;
    int max = 0;
    while (end < s.length()) {
        if (map[s.charAt(end)] == 0) {
            count++;
        }
        map[s.charAt(end)]++;
        if (count > k) {
            max = Math.max(max, end - start);
            while (count > k) {
                if (map[s.charAt(start)] == 1) {
                    map[s.charAt(start)]--;
                    count--;
                    if (count < k)
                        break;
                } else
                    map[s.charAt(start)]--;
                start++;
            }
        }
        end++;
    }
    max = Math.max(max, end - start);
    return max;
}

论坛里找到了一个最简的写法, 逻辑是基本一样的, 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
public int lengthOfLongestSubstringKDistinct(String s, int k) {
    int[] count = new int[256];
    int num = 0, i = 0, res = 0;
    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;
}