Longest Substring with At Most K Distinct Characters

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

Have you met this question in a real interview?
Example For example, Given s = "eceba", k = 3,

T is "eceb" which its length is 4.

Challenge O(n), n is the size of the string s.

Solution: Count char occurances

We can use a hash table to count distinct chars. We first add the number of char by one. Then we check the number of distinct chars, if it's larger than K. We decrement the count of the left char. And remember to erase the char from the table when it's value is zero, so we don't count it for distinct char. We move the left pointer of the sliding window forward by one position.

Time Complexity: O(N)

int lengthOfLongestSubstringKDistinct(string s, int k) {
    int left = 0, ans = 0;
    unordered_map<char, int> m;

    for (int i=0; i<s.size(); i++) {
        m[s[i]] += 1;

        while (m.size() > k) {
            m[s[left]] -= 1;
            if (m[s[left] == 0]) m.erase(s[i]);
            left += 1;
        }
    }
    return ans;
}

Solution: Save char index

Instead of saving count in hash table, we save the latest index of the char. When dictinct number of chars is larger than K, we start moving the left pointer of the sliding window. If the latest index of the left char is equal to the left pointer, we erase the char from the hash table.

int lengthOfLongestSubstringKDistinct(string s, int k) {
    int res = 0, left = 0;
    unordered_map<char, int> m;
    for (int i = 0; i < s.size(); ++i) {
        m[s[i]] = i;
        while (m.size() > k) {
            if (m[s[left]] == left) m.erase(s[left]);
            ++left;
        }
        res = max(res, i - left + 1);
    }
    return res;
}