Algorithm

LintCode/Longest Substring with At Most K Distinct Characters

Problem Summary

Given a string S and an integer K, find the length of the longest substring T that contains at most K distinct characters.

Solution

We can use two pointers, L and R, to mark the beginning and ending points of the current subsequence. Each time we greedily move R forward by 1, without breaking the rule that the substring contains at most K distinct characters. That is, if and only if the rule would not hold when R is moved forward, we move L forward too.

The time complexity is O(N).

Plus, there are some details with coding. In line 16 of the following code, if we replace the inequality with “r<s.length()”, there will be errors. Because r is of type “int” and s.length() is of type “unsigned int”, r will be converted to type “unsigned int” for the comparison. -1 will be converted to 4294967295, which is the maximum of unsigned int.

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
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    /*
     * @param s: A string
     * @param k: An integer
     * @return: An integer
     */
    int lengthOfLongestSubstringKDistinct(string &s, int k) {
    	if (s.length() == 0 || k <= 0)
    		return 0;
    	int l = 0, r = -1, ans = 0;
    	int total = 0, status[150];
    	memset(status,0,sizeof(status));
    	while (r<(int)s.length())
    	{
    		ans = max(ans,r-l+1);
    		if (r == s.length() - 1)
    			break;
    		++r;
    		if (status[s[r]] == 0)
    		{
    			++total;
    			while (total > k)
    			{
    				--status[s[l]];
    				if (status[s[l]] == 0)
    					--total;
    				++l;
    			}
    		}
    		
    		++status[s[r]];
    	}
    	return ans;
    }
};