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

Problem Overview: Given a string s, return the length of the longest substring that contains at most two distinct characters. The substring must be contiguous, so the goal is to scan the string while keeping track of how many unique characters appear in the current window.

Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)

Start every substring at index i and extend it character by character while tracking distinct characters with a small frequency map. As soon as the substring contains more than two unique characters, stop extending that window and move to the next starting index. During each expansion, update the maximum substring length that satisfies the constraint. This approach is straightforward and helps verify the constraint logic, but it repeatedly reprocesses overlapping substrings, making it inefficient for large inputs.

Approach 2: Sliding Window with Hash Map (O(n) time, O(1) space)

The optimal strategy uses the sliding window technique combined with a hash table. Maintain two pointers left and right that represent the current window. As you move right across the string, update a frequency map that counts how many times each character appears in the window.

If the map contains more than two distinct characters, the window becomes invalid. Shrink the window from the left by incrementing left and decrementing counts in the map until only two unique characters remain. At each step where the constraint is satisfied, update the maximum window length using right - left + 1.

The key insight: every character enters the window once and leaves once, so the two pointers each move at most n times. This guarantees linear time complexity. The frequency map stores at most three characters at any moment, so the space usage stays constant.

This pattern appears frequently in string and substring problems where the goal is to maintain a window that satisfies a constraint on distinct elements. Once you recognize the pattern, the implementation becomes a standard template.

Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the “at most K distinct characters” pattern and immediately move to a two-pointer window with a frequency map. Mentioning the brute force approach briefly shows that you understand the problem space, but implementing the O(n) sliding window demonstrates strong algorithmic intuition and familiarity with common substring optimization techniques.