340. Longest Substring with At Most K Distinct Characters

• Difficulty: Hard

• Topics: Hash Table, String, Sliding Window

• Similar Questions:

  • Longest Substring Without Repeating Characters

  • Longest Substring with At Most Two Distinct Characters

  • Longest Repeating Character Replacement

  • Subarrays with K Different Integers

  • Max Consecutive Ones III

Problem:

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

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

Solutions:

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        unordered_map<char, int> charCount;
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); ++right) {
            ++charCount[s[right]];
            if (charCount.size() <= k) {
                maxLen = max(maxLen, right - left + 1);
            } else {
                while (left <= right && charCount.size() > k) {
                    if(--charCount[s[left]] == 0)  charCount.erase(s[left]);
                    ++left;
                }
            }
        }

        return maxLen;
    }
};