Longest Substring with At Most K Distinct Characters

1. Handle k = 0

• If k is 0, no characters are allowed in the substring — return 0 immediately.

2. Initialize the Sliding Window

• Create a Map to track the frequency of each character in the current window.
• Set left to 0 and maxLen to 0.

3. Expand the Window

• Iterate right from 0 to s.length - 1.
• Add s[right] to the frequency map, incrementing its count.

4. Shrink When Invalid

• If the map has more than k distinct characters, the window is invalid.
• Shrink from the left: decrement the count of s[left]. If its count reaches 0, delete it from the map.
• Continue shrinking until the map size is at most k.

5. Update the Maximum

• After ensuring the window is valid, update maxLen with right - left + 1.

6. Return the Result

• After processing all characters, return maxLen — the length of the longest substring with at most k distinct characters.

Key Insight

This is the generalized version of the "at most 2 distinct characters" problem. The sliding window with a frequency map efficiently maintains the constraint by tracking exactly how many distinct characters are in the window. When a character's count drops to 0, removing it from the map ensures the map size accurately reflects the distinct character count. The overall time complexity is O(n) since each character is added and removed from the window at most once.