Longest Substring with At Most K Distinct Characters - Solution & Explanation

Problem Overview: Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters. The substring must be contiguous, so you need to track a valid window while ensuring the number of unique characters never exceeds k.

Approach 1: Brute Force Enumeration (O(n²) time, O(k) space)

Check every possible substring starting from each index. For a starting index i, expand the substring character by character while tracking distinct characters using a hash map or set. As soon as the number of unique characters exceeds k, stop expanding and move to the next starting index. During expansion, update the maximum substring length seen so far.

This method is straightforward and useful for understanding the constraint: every valid substring must contain at most k unique characters. However, it repeatedly scans overlapping ranges, which leads to O(n²) time in the worst case. Space complexity is O(k) because you store at most k distinct characters in the tracking structure. This approach works for small inputs but does not scale well for long strings.

Approach 2: Sliding Window + Hash Table (O(n) time, O(k) space)

The optimal solution uses the sliding window pattern with two pointers. Maintain a window defined by indices left and right. As you iterate the string with the right pointer, insert each character into a frequency map implemented with a hash table. This map tracks how many times each character appears inside the current window.

If the number of distinct characters becomes greater than k, shrink the window from the left. Decrease the frequency of s[left] in the map, remove it when the count reaches zero, and move the left pointer forward. Continue shrinking until the window again contains at most k distinct characters. At each step, compute the window length right - left + 1 and update the maximum.

Each character enters and leaves the window at most once. That means both pointers traverse the string only once, giving O(n) time complexity. The hash map holds at most k entries, so space complexity is O(k). This pattern appears frequently in string problems involving “longest substring with constraints”.

Recommended for interviews: Interviewers expect the sliding window + hash table solution. The brute force method shows you understand the constraint, but the optimal window approach demonstrates familiarity with two‑pointer techniques and efficient substring processing. Many substring problems reduce to the same pattern: expand the window to include characters, then contract it when constraints are violated.