340. Longest Substring with At Most K Distinct Characters

Posted on Edited on In

340. Longest Substring with At Most K Distinct Characters

Description

Given a string s and an integer k, return the length of the longest of s that contains at most k distinct characters.

Example 1:

1
2
3
Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Example 2:

1
2
3
Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.

Constraints:

  • 1 <= s.length <= 5 * 10^4
  • 0 <= k <= 50

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        map<char, int> freq;
        int left = 0, right = 0, n = s.size(), res = 0;
        while (right < n) {
            char& c = s[right++];
            freq[c]++;
            while (freq.size() > k) {
                char l = s[left++];
                freq[l]--;
                if (freq[l] == 0) {
                    freq.erase(l);
                }
            }
            res = max(res, right - left);
        }
        return res;
    }
};