Maximum Length Substring With Two Occurrences

Maximum Length Substring With Two Occurrences

What is this problem about?

The Maximum Length Substring With Two Occurrences coding problem asks for the length of the longest substring in which every character appears at most twice. This is a classic sliding window problem with a character frequency constraint, making it a clean introduction to variable-size window techniques for string problems.

Why is this asked in interviews?

Walmart Labs uses this problem as a warm-up for sliding window proficiency. It tests whether candidates can correctly maintain a character frequency map and shrink the window when a constraint is violated. The "at most twice" variant is slightly more complex than "all unique" but uses the same template, making it a good stepping stone for harder window problems.

Algorithmic pattern used

The solution uses a sliding window with a hash map. Maintain a left and right pointer. Expand the right pointer, adding s[right] to the frequency map. If any character's frequency exceeds 2, shrink the window by moving the left pointer right until the violation is resolved. At each step, track the maximum window size. This runs in O(n) time and O(1) space (since only 26 lowercase letters are tracked).

Example explanation

String: "aabcaab"

• Expand right: a→1, a→2, b→1, c→1. Window = "aabc", all ≤2. Length=4.
• Expand: a→3. Violation! Shrink: remove a at left (freq[a]=2). Left moves to index 1. Window = "abca". Length=4.
• Expand: a→3 again. Shrink: remove a at index 1 (freq[a]=2). Left moves to index 2. Window = "bcaa". Length=4.
• Expand: b→2. Window = "bcaab". All ≤2. Length=5.
• Maximum = 5.

Common mistakes candidates make

• Shrinking only once per violation: When a character exceeds 2, you must keep shrinking until the frequency drops back to 2, not just once.
• Not updating frequency when shrinking: Forgetting to decrement freq[s[left]] before moving left corrupts the window state.
• Using a set instead of a map: A set only tracks presence, not count. You need the frequency count to detect the "more than 2" condition.

Interview preparation tip

For the Hash Table Sliding Window String interview pattern, the sliding window template for frequency-constrained problems is: expand right, update map, while constraint violated: shrink left, update map. This exact template — with only the constraint changed — solves a wide family of problems: at most K distinct, at most 2 occurrences, all unique. Mastering it opens up dozens of interview problems.