Problem description:

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:

This problem is pretty similar to . Just change the checking size part to k.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        # use map to know distinct char in current substring
        # two pointer to know the left boundary
        l = 0
        res = 0
        bag = defaultdict(int)
        for i, c in enumerate(s):
            bag[c] += 1
            while len(bag) > k:
                # move left pointer until one of char is 0
                bag[s[l]] -= 1
                if bag[s[l]] == 0:
                    del bag[s[l]]
                l += 1
            res = max(res, i-l+1)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    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]];
            while (m.size() > k) {
                if (--m[s[left]] == 0) m.erase(s[left]);
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};