Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring without repeating characters.

For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1.

http://www.lintcode.com/en/problem/longest-substring-without-repeating-characters/

Discussion

假定string只有ASCII字符，用一个长为256的数组cnt存每个字符出现的个数，对当前字符c，若cnt[c]==0，distinct character number加1。问题的关键在于当该number>k的时候，怎么找到新substring的起始位置。用一个指针start指向substring的起始位置，移动start，移动过的字符cnt都减一，cnt为0的时候，distinct character number减1。

Solution

class Solution {
public:
    /**
     * @param s : A string
     * @return : The length of the longest substring 
     *           that contains at most k distinct characters.
     */
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        // write your code here
        int count[256];
        int numDistinct = 0, start = 0, maxlen = 0;
        for(int i=0; i<256; i++) 
            count[i] = 0;
        for (int i=0; i<s.length(); i++) {
            if(count[s[i]] ==0) {
                numDistinct++;
            }
            count[s[i]]++;
            while(numDistinct > k) {
                count[s[start]]--;
                if(count[s[start]] == 0) 
                    numDistinct--;
                start++;
            }
            if(i-start+1 > maxlen) {
                maxlen = i-start+1;
            }
        }
        return maxlen;
    }
};

O(n) runtime, O(1) sapce