Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Given a string, the goal is to find the length of the longest contiguous block of characters with no repeats.

The important word is contiguous. This is not asking for a subsequence that can skip characters. It is asking for one unbroken window inside the string.

So for abcabcbb, the answer is 3 because abc is the longest substring with all unique characters.

The key insight

This problem becomes much easier once it is viewed as a moving window.

While scanning from left to right, it only matters whether the current window still has all unique characters. If the next character is new, the window can grow. If the next character is a duplicate, the window must shrink from the left until the duplicate is no longer inside it.

That is the sliding-window idea.

The best version of that idea stores the last index where each character was seen. Then, instead of removing characters one by one, it can jump the left edge of the window directly past the duplicate.

How to derive the optimal solution

The brute-force approach is to check every substring and test whether it has repeated characters. That works, but it is far too slow because there are O(n^2) substrings and checking each one can take up to O(n).

The next step up is to notice that adjacent substrings overlap heavily. If a window is already known to contain no duplicates, then when one character is added on the right, only that new character can create a problem.

That leads to two sliding-window approaches:

  • A set-based window: move the left pointer forward one step at a time until the duplicate disappears.
  • A last-seen-index window: store the most recent position of each character and jump the left pointer directly.

Both run in O(n) time, but the last-seen-index version is usually the cleanest production solution because each step does constant work and handles repeated patterns like abba naturally.

The subtle but important rule is:

when a character was seen before, the left boundary should move to max(current_left, previous_index + 1).

That max matters because the previous occurrence might already be outside the current window. Without it, the window could move backward, which would be incorrect.

Best approaches

The set-based sliding window is a good way to discover the idea:

  • Time: O(n)
  • Extra space: O(min(n, charset))
  • Strength: conceptually simple

The last-seen-index sliding window is the best default:

  • Time: O(n)
  • Extra space: O(min(n, charset))
  • Strength: moves the left boundary in one jump and stays easy to reason about

Python solution

from typing import Dict


class Solution:
    def lengthOfLongestSubstring(self, text: str) -> int:
        last_seen_index_by_character: Dict[str, int] = {}
        window_start = 0
        best_length = 0

        for window_end, character in enumerate(text):
            window_start = self._advance_window_start(
                last_seen_index_by_character=last_seen_index_by_character,
                character=character,
                current_window_start=window_start,
            )

            current_window_length = window_end - window_start + 1
            best_length = max(best_length, current_window_length)
            last_seen_index_by_character[character] = window_end

        return best_length

    @staticmethod
    def _advance_window_start(
        last_seen_index_by_character: Dict[str, int],
        character: str,
        current_window_start: int,
    ) -> int:
        previous_index = last_seen_index_by_character.get(character)

        if previous_index is None:
            return current_window_start

        # Only move the window forward. If the old occurrence is already
        # outside the current window, it should not affect the answer.
        return max(current_window_start, previous_index + 1)

Why this works

At every step, the window is maintained so that it contains no repeated characters.

When a duplicate character appears, moving the left edge to one position after that character’s previous index is exactly enough to restore the invariant. Nothing earlier needs to be reconsidered, because every shorter left boundary would still include the duplicate.

The dictionary makes that update immediate, which is why the full scan stays linear.

Practical takeaway

This is one of the most important sliding-window problems because it teaches the pattern in its cleanest form:

  • keep a valid window
  • expand to the right
  • repair the window only when it becomes invalid
  • track the best window length seen so far

If the string problem involves a contiguous range and a constraint that can be enforced while moving two pointers, a sliding window is usually the first place to look.