Longest Two-Char Substring

Return the length of the longest substring of s containing at most two distinct characters.

longestTwoCharSubstring(s)

Input format: a single string (may be empty).

Examples

"eceba"    // → 3   ("ece")
"ccaabbb"  // → 5   ("aabbb")
"abc"      // → 2
""         // → 0

Walkthrough

Thinking it through

You want the longest substring using at most two distinct characters. Like "longest unique substring," checking every substring and counting distinct characters from scratch is O(n²) substrings, each costing up to O(n) — wasteful since neighboring windows share almost everything.

What you need to track as the window grows

The thing that can go wrong is the distinct-character count exceeding two. Keep a running frequency map of characters in the window — the number of keys is exactly the distinct count, no rescanning needed.

The specific shrink condition

The window becomes invalid the moment the map's key count reaches three. Remove characters from the left one at a time: decrement the leftmost's count, delete it if it hits zero, until at most two keys remain.

Building the approach

Expand by moving right forward, incrementing the new character's count.
While the map holds more than two keys, shrink from the left: decrement s[left]'s count, delete if zero, advance left.
Once valid again, compute the width and update the best if larger.
Repeat until right reaches the end.

Why this beats brute force

Each character enters once and leaves at most once, so both pointers move forward monotonically — O(n) total instead of O(n²). Using a map instead of rescanning is what makes each step O(1) amortized. This is a small variation on the unique-substring pattern: tracking "how many distinct" instead of "any duplicate," shrinking whenever the count crosses a threshold.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.