We need to find the longest contiguous portion of the string that uses no more than two different characters. The substring must be contiguous, meaning we can't skip characters. And "at most two distinct" means a substring with one distinct character (like "aaa") also counts.

For example, in "eceba", the substring "ece" works because it only uses 'e' and 'c'. We could also pick "eb" or "ba", but those are shorter. The moment we extend "ece" to "eceb", we have three distinct characters ('e', 'c', 'b'), which violates the constraint.

We are searching for a contiguous window with a constraint on its content: at most 2 distinct characters. A window that can grow on the right and shrink on the left fits a sliding window, which scans valid substrings without re-examining characters from scratch.

Key Constraints:

Intuition

Check every possible substring and find the longest one with at most two distinct characters. For each starting index, extend the substring character by character, tracking which distinct characters appear. The moment a third distinct character shows up, stop and move to the next starting index.

For each starting position, this measures how far the window can extend before it exceeds two distinct characters, then keeps the longest such length.

Algorithm

Visualization and Code

For each starting index, the inner loop re-scans the string from scratch, discarding the work done for the previous starting index. The next approach keeps a single window and only advances its left end when the constraint breaks, removing the repeated scanning.

Intuition

A sliding window maintains two pointers, left and right, that define the current window. We advance right to include more characters, and when the window holds more than 2 distinct characters, we advance left until it is valid again.

To know how many distinct characters the window holds, we keep a hash map from each character to its count inside the window. Adding a character increments its count; removing one (by advancing left) decrements it. When a count reaches zero, we drop that character from the map, so the number of keys equals the number of distinct characters.

Each character enters the window once (when right passes it) and leaves at most once (when left passes it), so both pointers together traverse the string in O(n).

Algorithm

Visualization and Code

The hash map approach is O(n) but shrinks the window one character at a time. The next approach tracks each character's last occurrence instead of its frequency, which lets left jump past an evicted character in a single step.

Intuition

Instead of tracking the frequency of each character, track the index of its last occurrence within the window. When a third distinct character appears, find which of the two existing characters has the earliest last occurrence and move left directly past that position.

This replaces the inner while loop with a single jump. The character with the earliest last occurrence is the one whose run ends first inside the window, so every position up to and including its last occurrence belongs to that character and must be dropped to remove it. Jumping left to that index plus one removes exactly that character and keeps the other two.

Both approaches are O(n). This one avoids stepping through the discarded positions one at a time, though it does a small scan over the map's entries on each eviction.

Algorithm

Visualization and Code