Longest Substring with At Most K Distinct Characters

Longest Substring with At Most K Distinct Characters

What is this problem about?

The Longest Substring with At Most K Distinct Characters interview question asks you to analyze a string and find the length of the longest contiguous sequence of characters that contains K or fewer unique characters. For instance, if s = "eceba" and k = 2, the longest substring with at most 2 distinct characters is "ece", which has a length of 3.

Why is this asked in interviews?

This problem is the gold standard for testing the Sliding Window and Hash Map patterns. It is a highly practical question; similar logic is used in data streaming and network packet analysis where memory constraints limit the number of unique identifiers you can track at once. Interviewers use it to see if you can efficiently expand a range and concisely shrink it when constraints are violated.

Algorithmic pattern used

This utilizes the Sliding Window pattern coupled with a Hash Table (or dictionary). You maintain a window using left and right pointers. As you move right, you add the character to the Hash Table and increment its frequency. If the size of the Hash Table (the number of distinct characters) exceeds K, you increment the left pointer, decreasing the frequency of the left character in the Hash Table. Once a character's frequency hits 0, you remove it from the table.

Example explanation

String s = "eceba", K = 2.

• right = 0 ('e'): Map {e:1}. Size 1 $\le 2$. MaxLen = 1.
• right = 1 ('c'): Map {e:1, c:1}. Size 2 $\le 2$. MaxLen = 2.
• right = 2 ('e'): Map {e:2, c:1}. Size 2 $\le 2$. MaxLen = 3. ("ece")
• right = 3 ('b'): Map {e:2, c:1, b:1}. Size 3 $> 2$. Invalid!
  • We must shrink. Move left (0). Remove 'e'. Map {e:1, c:1, b:1}. Still invalid.
  • Move left (1). Remove 'c'. Map {e:1, b:1}. Valid! Window is "eb".
• right = 4 ('a'): Map {e:1, b:1, a:1}. Size 3 $> 2$. Invalid.
  • Move left. Window shrinks to "ba". The maximum length recorded was 3.

Common mistakes candidates make

A very common mistake is shrinking the window incorrectly. Candidates sometimes move the left pointer and decrement the character count, but forget to explicitly delete or remove the key from the Hash Table when its count reaches 0. If the key remains with a value of 0, map.size() will still report the character as a distinct entity, breaking the core logic of the algorithm.

Interview preparation tip

To ace the Longest Substring with At Most K Distinct Characters coding problem, practice writing clean while loops for shrinking the window. The structure should always be: while (map.size() > k) { decrement char at left; if (count == 0) map.delete(char); left++; }. This precise sequence guarantees your window evaluates state correctly at every step.