PU Longest Substring with At Most K Distinct Characters

Jan 01, 1970

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.

Solution:

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if k < 1: return 0
        ht = {}
        i = 0
        res = 0
        for j, c in enumerate(s):
            ht[c] = j
            if len(ht) < k + 1: continue
            res = res if res > j - i else j - i
            i = min(ht.values())
            del ht[s[i]]
            i += 1
        res = res if res > len(s) - i else len(s) - i
        return res
int lengthOfLongestSubstringKDistinct(char* s, int k) {
    int count[256] = {0};
    int l = 0, res = 0, already = 0;
    int r;
    for (r = 0; s[r]; r++) {
        if (count[s[r]]++ == 0) already++;
        if (already < k + 1) continue;
        res = res > r - l ? res : r - l;
        while (--count[s[l++]] > 0);
        already--;
    }
    return res > r - l ? res : r - l;
}

Summary:

  1. Python: 82ms, 95.84%
  2. C: 3ms, 16.87%
  3. It's not hard, at most two pass. O(N)