Maximum Length Substring With Two Occurrences - Solution & Explanation

Problem Overview: Given a string s, find the maximum length of a substring where every character appears at most two times. The substring must remain contiguous, so the challenge is maintaining character counts while expanding or shrinking the window efficiently.

Approach 1: Sorting and Two-Pointers (O(n log n) time, O(n) space)

This approach conceptually groups characters and uses a two-pointer style scan to maintain a valid segment where no character frequency exceeds two. After sorting auxiliary structures that track characters and indices, you move two pointers to maintain the longest valid span. When a character appears more than twice, shift the left pointer forward until the constraint is restored.

The core idea is similar to classic two pointers problems: expand the right pointer to include new characters and shrink the left pointer when constraints break. Sorting helps organize character occurrences but adds extra overhead. Time complexity is O(n log n) due to sorting, and space complexity is O(n) for auxiliary storage.

This method demonstrates the constraint-handling logic clearly but is rarely the optimal implementation because the substring is already sequential in the original string.

Approach 2: HashMap Sliding Window (O(n) time, O(1) space)

The optimal solution uses a sliding window combined with a frequency map. Maintain two pointers left and right that define the current substring. As you expand right, increment the count of s[right] in a hash table. If any character count exceeds two, move left forward while decrementing frequencies until the substring becomes valid again.

At every step, compute the window size right - left + 1 and update the maximum length. Each character enters and leaves the window at most once, which guarantees linear time. Because the alphabet size is bounded (typically lowercase English letters), the space complexity is effectively O(1).

This pattern appears frequently in substring problems where you enforce limits on character frequency. The sliding window ensures you never reprocess characters unnecessarily, making it both efficient and easy to implement.

Recommended for interviews: The sliding window with a hash map is the expected solution. Interviewers want to see that you recognize substring constraint problems and immediately apply the sliding window pattern. Explaining a brute-force idea or a less optimal pointer approach shows understanding, but implementing the O(n) window solution demonstrates strong problem-solving instincts.