Longest Substring Without Repeating Characters

Find the length of the longest substring with no repeated characters.

Return the length of the longest substring without repeated characters. This is the cleanest sliding-window problem for learning how to shrink only when the window becomes invalid.

StringSliding Window

Pattern fit

The substring must stay contiguous, and the only thing that breaks validity is repetition inside the current window, which makes shrink-on-invalid sliding window the natural fit.

Key observation

Once a character repeats, moving the left boundary forward is the only way to restore validity; no other operation can help.

Target complexity

O(n) / O(k)

How to break down the solution cleanly

Use a set to represent which characters are currently inside the window.

Expand the right pointer one character at a time.

If the new character already exists, keep removing characters from the left until the duplicate disappears.

After the window becomes valid again, update the best length.

Walk through one example

Example: s = "abcabcbb".

Window grows through "abc" and best becomes 3.

When the second 'a' arrives, move left until the first 'a' is removed, then continue.

No later window exceeds length 3, so answer stays 3.

Reference implementation

Python

def lengthOfLongestSubstring(s: str) -> int:
    seen = set()
    left = 0
    best = 0

    for right, char in enumerate(s):
        while char in seen:
            seen.remove(s[left])
            left += 1

        seen.add(char)
        best = max(best, right - left + 1)

    return best

TypeScript version

TypeScript

function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right += 1) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left += 1;
    }

    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }

  return best;
}

What to pay attention to in the code

codeThe answer should be updated only after duplicates are fully removed.
codeEvery character is added and removed at most once, so total time is O(n).

Common pitfalls

warning

Using a set without removing left-side characters correctly.

warning

Updating the best length before duplicates are cleared.

Common follow-ups

How would you return the substring itself, not just the length?

How does the solution change if at most k distinct characters are allowed?

Continue with related problems

Build repeatable depth inside the Sliding Window cluster before moving on.

view_weekBack to the pattern page

#76