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.

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 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.

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

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.