Longest Substring with At Most K Distinct Characters

How it works

An optimization on the standard sliding window: instead of shrinking the window with a while loop, we only shrink by one step when invalid. This keeps the window size from ever decreasing by more than one, which means we only need to track when the window grows. The final answer is the maximum window size achieved, which equals n - left at the end.

Steps

1. Initialize maxSize = 0 and a hash map counter.
2. For each right from 0 to n-1:
   • Add s[right] to the counter.
   • If distinct characters exceed k:
     • Decrement count of s[right - maxSize] (the leftmost character of current max window).
     • Remove from map if count is 0.
   • Otherwise, increment maxSize.
3. Return maxSize.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Where n is the length of the input string s and k is the maximum number of distinct characters.

Things to watch for

Not Removing Zero-Count Characters from the Map

When shrinking the window and decrementing character counts, failing to remove characters with zero count from the hash map leads to incorrect distinct character counts. Always delete or remove entries when their count reaches zero to maintain an accurate count of distinct characters in the current window.

Off-by-One Errors in Window Size Calculation

A frequent mistake is calculating the window size as right - left instead of right - left + 1. Since both left and right are inclusive indices, the correct window size includes both endpoints. This off-by-one error leads to returning a result that is one less than the actual answer.

Handling Edge Cases with k = 0

When k is zero, no characters are allowed in the substring, so the answer should be 0. Some solutions forget to handle this edge case, leading to incorrect results or infinite loops when the while condition never terminates because the window can never be valid.

import collections

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        max_size = 0
        counter = collections.Counter()

        for right in range(len(s)):
            counter[s[right]] += 1

            if len(counter) <= k:
                max_size += 1
            else:
                counter[s[right - max_size]] -= 1
                if counter[s[right - max_size]] == 0:
                    del counter[s[right - max_size]]

        return max_size

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int n = s.length();
        int maxSize = 0;
        unordered_map<char, int> counter;

        for (int right = 0; right < n; right++) {
            counter[s[right]]++;

            if (counter.size() <= k) {
                maxSize++;
            } else {
                counter[s[right - maxSize]]--;
                if (counter[s[right - maxSize]] == 0) {
                    counter.erase(s[right - maxSize]);
                }
            }
        }
        return maxSize;
    }
};