Longest Substring Without Repeating Characters

Find the longest substring with no repeated character.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Longest Substring Without Repeating Characters: Keep [L..R] duplicate-free by jumping L past a repeated character that is still inside the window.

Input and goalFind the longest substring with no repeated character.

Initialize the empty historyFor text "abba", start L = 0, best = 0, and inspect R = 0.

LRa0b1b2a3

rangeempty before reading index 0best0

saved stateempty

Recognize it

Use it when the answer is a longest contiguous span constrained by uniqueness and a repeated value tells exactly how far the left boundary can safely jump.

Keep true

After processing index R, [L..R] has no repeated character; L never moves backward, and best is the maximum length of every valid window ending at or before R.

Reuse it

For longest windows repaired by the newest violation, store enough history to jump over the violating occurrence, but clamp the new left boundary so stale history can never move it backward.

Pattern: Sliding window with last positions.

Simple idea: When a repeated character is inside the current window, move left to one position after its last copy. Never move left backward.

def length_of_longest_substring(text: str) -> int:
   last_seen: dict[str, int] = {}
   left = 0
   best = 0

   for right, char in enumerate(text):
      if char in last_seen:
         left = max(left, last_seen[char] + 1)
      last_seen[char] = right
      best = max(best, right - left + 1)

   return best

Cost: $O(n)$ time and $O(k)$ space.