[LintCode] Problem 386 - Longest Substring with At Most K Distinct Characters

Posted on | In ,

Given a string S, find the length of the longest substring T that contains at most k distinct characters.

Example

No.1

Input: S = “eceba” and k = 3

Output: 4

Explanation: T = “eceb”

No.2

Input: S = “WORLD” and k = 4

Output: 4

Explanation: T = “WORL” or “ORLD”

Challenge

O(n) time

Code

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) {
    int result = 0;
    int[] count = new int[128];
    int num = 0;
    int start = 0;
    int end = 0;

    while (end < s.length()) {
        int idxEnd = s.charAt(end) - '0';

        if (count[idxEnd] == 0)
            num++;

        count[idxEnd]++;
        end++;

        while (num > k) {
            int idxStart = s.charAt(start) - '0';
            count[idxStart]--;

            if (count[idxStart] == 0)
                num--;

            start++;
        }

        result = Math.max(result, end - start);
    }

    return result;
}