You are given a string s and an integer k. Your task is to find the length of the longest substring within s that contains at most k distinct characters.

A substring is a contiguous sequence of characters within the string. For example, if s = "eceba" and k = 2, you need to find the longest substring that has no more than 2 different characters.

Let's break down what this means:

• You need to examine all possible substrings of the input string s
• Count the number of distinct/unique characters in each substring
• Keep only those substrings where the distinct character count is at most k (less than or equal to k)
• Return the length of the longest valid substring

For instance:

• If s = "eceba" and k = 2, the substring "ece" has 2 distinct characters ('e' and 'c'), making it valid with length 3
• If s = "aa" and k = 1, the entire string has only 1 distinct character ('a'), so the answer would be 2

The solution uses a sliding window technique with a hash table to efficiently track the distinct characters in the current window. The window expands by moving the right boundary and contracts from the left when the distinct character count exceeds k. The final answer is calculated as the length of the string minus the final position of the left boundary, which gives us the maximum valid window size encountered.

When we need to find the longest substring with a certain property, the sliding window technique often comes to mind. The key insight here is that we want to maintain a window that always satisfies our constraint (at most k distinct characters).

Think about it this way: if we have a valid window with at most k distinct characters, we want to expand it as much as possible to maximize its length. We keep expanding the right boundary by including more characters. However, once we include a character that causes us to exceed k distinct characters, we need to shrink from the left.

The clever part of this solution is recognizing that we don't need to track the maximum length explicitly. Instead, we can maintain a window that grows to the maximum possible size and then slides along the string while maintaining that size (or growing larger if possible).

Here's the key observation: once we find a valid window of a certain size, we never need to consider windows smaller than that size again. So when we need to shrink the window due to having too many distinct characters, we only shrink it by exactly one position from the left. This ensures our window either maintains its current size or grows larger.

By the end of the iteration, the window size (which is len(s) - l where l is the left boundary) represents the maximum valid window we've encountered. The hash table cnt helps us efficiently track how many distinct characters are in our current window, and we remove characters from it when their count drops to zero as we slide the left boundary forward.

This approach is optimal because we visit each character at most twice (once when expanding right, once when shrinking from left), giving us O(n) time complexity.

Watch the window grow and slide across the string — step through it below, then read the mechanics.

The solution uses a sliding window technique combined with a hash table to efficiently solve this problem. Let's walk through the implementation step by step:

Data Structures Used:

• A hash table cnt (Counter in Python) to track the frequency of each character in the current window
• A variable l to mark the left boundary of the sliding window

Algorithm Steps:

1. Initialize the window: Start with l = 0 as the left boundary and an empty Counter cnt to track character frequencies.

2. Expand the window: Iterate through each character c in the string s (this implicitly represents the right boundary of our window):

   Copy
   for c in s:
       cnt[c] += 1

   Add each character to our frequency counter.

3. Check constraint and shrink if needed: After adding a character, check if we've exceeded k distinct characters:

   Copy
   if len(cnt) > k:
       cnt[s[l]] -= 1
       if cnt[s[l]] == 0:
           del cnt[s[l]]
       l += 1

   • If len(cnt) > k, we have too many distinct characters
   • Decrease the count of the character at position l (left boundary)
   • If that character's count becomes 0, remove it from the hash table entirely
   • Move the left boundary one position to the right

4. Calculate the result: After processing all characters, the maximum window size is:

   Copy
   return len(s) - l

   This works because the window maintains the maximum valid size it has seen. The final window spans from position l to the end of the string.

Why this works:

• The window never shrinks below the maximum valid size found so far
• When we encounter too many distinct characters, we only shrink by exactly one position
• This ensures we're always maintaining or growing toward the maximum possible window size
• The time complexity is O(n) since each character is visited at most twice
• The space complexity is O(min(n, σ)), where σ is the alphabet size: the window is allowed to slide while invalid, so the hash table can hold more than k + 1 distinct characters (for s = "aaabc" and k = 1 the final window "abc" holds 3)