4.6.2 — Longest Substring Without Repeating Characters

LeetCode 3 · Medium · ★ Blind 75

The problem

Return the length of the longest stretch of the string with no repeated character. The stretch must be contiguous.

"abcabcbb"  →  3    ("abc")
"bbbbb"     →  1    ("b")
"pwwkew"    →  3    ("wke", not "pwke" — that is a subsequence, not a substring)

Up to 50,000 characters, any printable ASCII.

Constraints:

• The string can contain letters, numbers, symbols, and spaces.
• Length can be up to 50,000.

Plain English: Find the longest possible slice of a string where no character appears more than once.

The naive approach

The brute-force way is to check every possible substring. You pick a starting index, pick an ending index, and then loop through that substring to see if it has duplicates (e.g., using a hash set).

• Why it fails: Generating every substring takes O(n^2) time. Checking each one for duplicates takes O(n) time. Overall, that's O(n^3). Even if you optimise the checking to O(n^2), with 50,000 characters, 50,000^2 = 2.5 billion operations. It's too slow.

The pattern

The word contiguous is the cue. Whenever a problem asks for the longest or shortest contiguous stretch that satisfies some condition, the answer is a sliding window.

A window is two indices, left and right, marking a stretch of the string. Both only ever move forwards. The rule is always the same shape:

• Extend the right edge by one, always.
• While the window breaks the condition, pull the left edge in.
• After fixing it, record the window size.

Here the condition is "no repeated character", so the window is repaired by dropping characters off the left until the duplicate is gone.

The ELI5 Analogy: Imagine you're sliding a rectangular magnifying glass over a line of letters. The glass grows to the right as long as every letter inside is unique. Suddenly, a letter appears on the right that matches one already inside the glass. The glass is now "broken." The only way to fix it is to pull the left edge of the glass inward, dropping letters, until that offending duplicate is left behind. Then you can go back to growing the right edge.

The solution

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        window = set()
        left = 0
        best = 0

        for right in range(len(s)):
            while s[right] in window:        # the new character breaks the rule
                window.remove(s[left])       # so shrink from the left
                left += 1
            window.add(s[right])
            best = max(best, right - left + 1)

        return best

TypeScript

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

  for (let right = 0; right < s.length; right++) {
    while (window.has(s[right])) {
      window.delete(s[left]);
      left++;
    }
    window.add(s[right]);
    best = Math.max(best, right - left + 1);
  }

  return best;
}

right - left + 1 is the window length. The + 1 is there because both ends are included — a window from index 2 to index 4 holds three characters.

The while shrinks by exactly as much as needed and no more. It stops the moment the duplicate character has been dropped, which is always before or at the position where that character last appeared.

Code Walkthrough

• window = set(): A hash set to keep track of the characters currently inside our window. Lookups and removals are O(1).
• left = 0: The left edge of our window.
• for right in range(len(s)):: The right edge of our window moves forward exactly one step per loop iteration.
• while s[right] in window:: Before we can officially add the new character s[right], we must ensure it doesn't create a duplicate. If it's already in our set, the window is invalid.
• window.remove(s[left]); left += 1: We shrink the window from the left, removing characters from the set one by one, until the duplicate is gone.
• window.add(s[right]): Now that the window is valid, we can safely add the new character.
• best = max(...): We update our record for the longest valid window seen so far.

Trace

s = "pwwkew"

right	char	window before	action	window after	best
0	p	{}	add	{p}	1
1	w	{p}	add	{p,w}	2
2	w	{p,w}	drop p, drop w, then add	{w}	2
3	k	{w}	add	{w,k}	2
4	e	{w,k}	add	{w,k,e}	3
5	w	{w,k,e}	drop w, then add	{k,e,w}	3

Edge cases

• Empty string: "". The loop never runs, returning 0.
• All identical characters: "bbbbb". The right pointer moves forward, adds "b", then the next step sees "b" is in the set. It forces the left pointer to move, removing the old "b". The window size never exceeds 1.
• No repeats at all: "abcdef". The while loop never executes. The right pointer just marches to the end, and the answer is the full length of the string.

Complexity

O(n) time, even though there is a while inside a for.

The argument is the same one as 4.4.9. left only ever moves forward, and it can never pass right, so across the entire run it advances at most n times in total. It is not n times per outer iteration. So the loops add up to O(n) rather than multiplying to O(n^2).

Say this proof out loud. The code looks quadratic and an interviewer will ask.

O(k) space for k distinct characters, which is O(1) if the alphabet is bounded.

The faster variant: jump instead of shrink

Instead of stepping left forward one character at a time, remember where each character was last seen and jump straight past it.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last_seen = {}
        left = 0
        best = 0

        for right, c in enumerate(s):
            if c in last_seen and last_seen[c] >= left:      # the guard
                left = last_seen[c] + 1
            last_seen[c] = right
            best = max(best, right - left + 1)

        return best

The >= left guard is essential and easy to forget. The map holds every character ever seen, including ones that have already fallen out of the window. Without the guard, an old position drags left backwards, the window grows past a duplicate, and the answer comes out too large.

Try "abba" without the guard. At the final a, the map says a was last at index 0. Since left is already 2, jumping to 0 + 1 = 1 moves it backwards and the window becomes "bba", which contains a repeat.

Both versions are O(n). This one does fewer operations, and the guard is the price.

Where this goes next

Change only the condition and the same skeleton solves a family:

• at most k distinct characters — shrink while the map has more than k keys.
• exactly k distinct characters — count "at most k" minus "at most k−1". That trick converts a hard exact condition into two easy ones and is worth remembering.
• Longest Repeating Character Replacement — shrink while the characters you would need to change exceed k. That is 4.6.3.
• Minimum Window Substring — the shortest window rather than the longest, which flips where you record the answer. 4.6.5.

What the interviewer will push on

"Why is this O(n) and not O(n^2)?" The left pointer only moves forwards and never passes right, so it advances at most n times overall.

"Substring or subsequence?" Substring, meaning contiguous. "pwke" is not an answer. Say this back to them before coding — it is a genuine ambiguity in the wording and checking it costs five seconds.

"What if you also had to return the substring itself?" Store the left index when you update best, then slice at the end.

"What if the alphabet is Unicode?" The set and map still work; only a fixed-size array solution would break.

One thing to volunteer: name the window rule before writing it. "Extend right always; shrink left while the window is invalid; record after repairing." Every problem in this chapter is that sentence with a different definition of invalid.

Next: 4.6.3 Longest Repeating Character Replacement — the same window with a condition that is genuinely subtle, and a famous shortcut that looks wrong.