Maximum Length Substring With Two Occurrences

Introduction

Sliding window problems have a way of exposing exactly how well you understand time complexity — not in theory, but under pressure. "Maximum Length Substring With Two Occurrences" is one of those problems that looks harmless on a whiteboard and then quietly punishes any solution that re-scans the same characters over and over.

Interviewers like this problem because it tests three things at once: whether you can recognize when brute force is going to blow up, whether you understand why a sliding window collapses cubic time down to linear, and whether you can implement the shrink step correctly — which, as you'll see, is where most people trip up.

Beyond interviews, this exact pattern shows up constantly in real systems: rate limiters that allow a request twice but not a third time in a window, log deduplication that suppresses a repeated error after two occurrences, and cache eviction policies that track recent access counts. Learning this problem well means learning a pattern you'll reuse for years.

Problem Overview

You're given a string. You need to find the length of the longest contiguous substring in which no character appears more than twice.

That's the entire constraint: every character in your window is allowed to show up once or twice, but the moment a third occurrence of any character enters the window, that window is no longer valid.

You're not looking for the substring itself — just its length. And you're not restricted to a specific alphabet; the technique works for any set of characters, though the implementation below assumes lowercase English letters for simplicity.

Example

Take the string:

c e b a b c a c b

The substring b a b c a c is valid — b appears twice, a appears twice, c appears twice. Nothing exceeds the limit.

But extend it by one more character and c shows up a third time. The window is now broken, and you'd need to shrink from the left until it's legal again.

A second example makes the edge case obvious: for the string bcbbbcba, the answer is 4 (the window b c b a, found starting at index 4). For aaaa, the answer is 2 — no matter how long a run of identical characters is, only two of them can ever coexist in a valid window.

Intuition

Here's the discovery process an experienced engineer goes through, roughly in order:

First, they notice the problem is really about counting characters within a bounded region, not about characters in isolation. That's the first hint that some kind of window — not a single pass — is needed.

Second, they ask: what happens if I check every possible substring? They quickly realize that's wasteful, because most substrings overlap heavily with substrings they've already checked. If [0, 5] is valid, checking [0, 4] from scratch again is pure waste — you already know almost everything about it.

Third, and this is the key insight: a window only ever needs to grow from the right and shrink from the left. You never need to jump around inside it. If adding a new character breaks the rule, the fix is always to remove characters from the left edge — never to restart the scan somewhere in the middle.

That single realization is what turns this into a two-pointer, one-pass algorithm. You don't need a heap, you don't need dynamic programming — you need one dictionary to track counts and two pointers to define the window's boundaries.

Brute Force Solution

Idea: Check every possible substring, count the characters inside each one, and verify none exceeds two occurrences.

Algorithm:

1. For every starting index i from 0 to n-1:
2. For every ending index j from i to n-1:
3. Count every character in the substring s[i:j+1].
4. If no character exceeds two occurrences, compare its length against the best found so far.

Advantages: Trivial to reason about and verify correctness on small inputs.

Disadvantages: Extremely wasteful — the same characters get re-counted across overlapping substrings thousands of times.

Time complexity: O(n²) substrings, each requiring O(n) to count characters → O(n³) overall.

Space complexity: O(k) for the counting structure per substring, where k is the alphabet size — negligible next to the time cost.

This passes on toy examples and times out the instant the interviewer hands you a string with a few thousand characters.

Optimal Solution

The optimal approach is the sliding window (sometimes called the "elastic window") pattern.

Maintain:

• A dictionary count mapping each character to how many times it appears in the current window.
• A left pointer marking the start of the window.
• A best variable tracking the longest valid window seen so far.

Walk a right pointer across the string, one character at a time:

Step	Action
1	Add s[right] to the window, incrementing its count.
2	While count[s[right]] > 2, remove s[left] from the window and advance left.
3	The window [left, right] is now guaranteed valid — update best with its size.

The critical property that makes this O(n): every character enters the window exactly once (from the right) and leaves at most once (from the left). There's no re-scanning, no restarting — the window only ever shrinks by exactly the amount needed to make it legal again, then keeps growing.

Python Code

def max_substring_two_occurrences(s: str) -> int:
    """Return the length of the longest substring where no character
    appears more than twice."""
    counts = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        counts[char] = counts.get(char, 0) + 1

        # Shrink from the left until the window is valid again.
        while counts[char] > 2:
            left_char = s[left]
            counts[left_char] -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

Code Walkthrough

• counts = {} — the single dictionary tracking how many times each character currently appears inside the window.
• left = 0 — the left boundary of the window; it only ever moves forward.
• for right, char in enumerate(s) — grows the window one character at a time from the right.
• counts[char] = counts.get(char, 0) + 1 — .get(char, 0) returns 0 if the character hasn't been seen yet, so this line safely initializes and increments in one step.
• while counts[char] > 2 — a while, not an if, because a long run of the same character (like aaaa) may need several shrink steps in a row to become valid again.
• counts[left_char] -= 1; left += 1 — removes the leftmost character from the window and advances the boundary.
• best = max(best, right - left + 1) — only runs after the window is confirmed valid, so it never scores an illegal window. right - left + 1 is just the window's size.

Dry Run

String: b c b b b c b a, indices 0–7.

right	char	counts after add	shrink?	left after	window	best
0	b	{b:1}	no	0	[0,0]	1
1	c	{b:1,c:1}	no	0	[0,1]	2
2	b	{b:2,c:1}	no	0	[0,2]	3
3	b	{b:3,c:1}	yes → remove s[0]=b	1	{b:2,c:1}, [1,3]	3
4	b	{b:3,c:1}	yes → remove s[1]=c, s[2]=b	3	{b:1}, [3,4]	2
5	c	{b:1,c:1}	no	3	[3,5]	3
6	b	{b:2,c:1}	no	3	[3,6]	4
7	a	{b:2,c:1,a:1}	no	3	[3,7]	5

Wait — checking against the transcript's stated final window b c b a (indices 4–7), let's recheck step 4 carefully: at right=4, char = s[4] = b, counts[b] becomes 3 (it was 2 after index 2, then 3 at index 3 which triggered one shrink to 2, then index 4 pushes it back to 3). The while loop removes s[left] repeatedly — starting at left=1 (c), then left=2 (b) — until counts[b] drops to 2, landing left=3. Window becomes [3,4] = b, b — wait, s[3] and s[4] are both b. Let me re-index against the actual string b c b b b c b a: s[0]=b, s[1]=c, s[2]=b, s[3]=b, s[4]=b, s[5]=c, s[6]=b, s[7]=a.

At right=4, window before shrink is [1,4] = c b b b, counts b:3, c:1. Shrink: remove s[1]=c → counts c:0, left=2; b still 3. Remove s[2]=b → counts b:2, left=3. Stop. Window is [3,4] = b b, size 2.

Continuing: right=5 (c) → window [3,5] = b b c, counts b:2,c:1, valid, size 3. right=6 (b) → counts b:3 → shrink: remove s[3]=b, left=4, counts b:2. Window [4,6] = b b c, size 3. right=7 (a) → window [4,7] = b b c a... but that has b:2, c:1, a:1 — wait s[4]=b, s[5]=c, s[6]=b, s[7]=a → b c b a, size 4. Best = 4.

This matches the video's stated answer exactly: the final window is indices 4–7, b c b a, length 4.

Complexity Analysis

Time: O(n). The right pointer advances exactly n times. The left pointer only ever moves forward and can advance at most n times total across the entire run — it never resets or moves backward. Total work is bounded by 2n operations, which is O(n).

Space: O(1) in practice for a fixed alphabet (at most 26 entries for lowercase English letters), or O(k) in general where k is the alphabet size — independent of the string's length.

These bounds are tight because every character is visited a constant number of times regardless of input size, which is the defining property of a correctly implemented sliding window.

Alternative Solutions

If the input is restricted to lowercase English letters, you can replace the dictionary with a fixed-size list of 26 counters, indexed by ord(char) - ord('a'). This keeps the same O(n) time complexity but trades dictionary hashing overhead for direct array indexing, which is marginally faster in practice. It's a small optimization, but worth knowing — most people reach for a dictionary out of habit even when the alphabet is small and fixed.

For the generalized version of this problem — "at most k occurrences" instead of a fixed two — the exact same window and dictionary logic applies. You only change the shrink condition from counts[char] > 2 to counts[char] > k.

Edge Cases

• Empty string — returns 0, since the loop never executes.
• String where every character already appears twice or fewer — the entire string is one valid window; the function returns the full length.
• String of a single repeated character (e.g., aaaa) — always caps out at 2, since a third occurrence of the same character immediately triggers a shrink.
• All unique characters — no shrinking ever happens; the window grows to cover the whole string.
• Single-character string — returns 1.

Common Mistakes

1. Shrinking with if instead of while. A run of three or more identical characters needs multiple shrink steps in a single iteration — an if only removes one character and leaves the window still invalid.
2. Updating best before the shrink loop finishes. This can score a window that's still technically illegal.
3. Forgetting to decrement the count when removing from the left. Without this, the dictionary drifts out of sync with the actual window contents.
4. Using counts[char] directly instead of counts.get(char, 0) when incrementing, which throws a KeyError on a character's first appearance.
5. Comparing window validity using the wrong character — the shrink condition must check the count of the character that was just added, not some other character in the window.

Interview Questions

• How would you modify this to allow "at most k" occurrences instead of exactly two?
• What if the alphabet includes uppercase letters, digits, or Unicode — does your solution still hold?
• Can you solve this without a dictionary, using only fixed-size arrays?
• What's the maximum number of times the left pointer can move across the entire algorithm, and why does that bound the time complexity?
• How would this change if you needed to return the substring itself, not just its length?

Similar Problems

• Longest Substring Without Repeating Characters (LeetCode 3) — the same sliding window pattern with a limit of one occurrence instead of two.
• Longest Substring with At Most K Distinct Characters — shifts the constraint from occurrence count to distinct character count, but uses the identical shrink-on-violation structure.
• Fruit Into Baskets (LeetCode 904) — a disguised version of "at most 2 distinct characters," solvable with the same window technique.
• Max Consecutive Ones III — a binary-array variant of the same shrinking window idea.

Key Takeaways

The core lesson here isn't the specific problem — it's recognizing when a nested-loop brute force is secretly a sliding window in disguise. Any time you're checking substrings or subarrays against a bounded constraint (occurrence count, sum, distinct elements), ask whether the window can only ever grow from one side and shrink from the other. If so, you almost never need to re-scan anything, and the solution collapses to O(n).

Watch the Video

For the full visual walkthrough — including the trace through bcbbbcba step by step, the quiz rounds, and the no-dictionary array variant — watch the video here: {LINK}

About the Series

This article is part of Fun with Learning Technology, a series built to turn interview panic into patterns that actually stick. Instead of memorizing individual problems, each episode breaks down the underlying technique — sliding windows, two pointers, dynamic programming, graph traversal — so you can recognize it instantly the next time it shows up wearing a different costume.

Call To Action

If this breakdown helped the pattern click, drop a like on the video and subscribe on YouTube — new episodes cover a fresh interview pattern every week. For deeper written breakdowns like this one, subscribe to the Substack. And if you've got a problem you'd like covered next, or you spotted a cleaner approach, leave a comment — I read every one.

---

def max_length_substring(s):
    count = {}
    left = 0
    best = 0
    for right in range(len(s)):
        c = s[right]
        count[c] = count.get(c, 0) + 1
        while count[c] > 2:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best