340. Longest Substring with At Most K Distinct Characters (Hard)

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: Hash Table 16ms

int lengthOfLongestSubstringKDistinct(string s, int k) {
    if (k == 0) return 0;
    unordered_map<char, int> m;
    int start = 0, res = 0;
    for (int i = 0; i < s.size(); ++i) {
        ++m[s[i]];
        // discint k has been reached, cannot add new characters
        while (m.size() > k) {
            // remove the one char in current substring
            if (--m[s[start]] == 0) m.erase(s[start]);
            ++start;
        }
        res = max(res, i-start+1);
    }

    return res;
}

Follow up:

$$O(nlogk)$$