Frontend Beauty
ESC

Type to search the knowledge base.

Longest Substring Without Repeating

Find the longest substring with all unique characters — sliding window with a last-seen map, O(n) time.

intermediate3 min read
  • dsa
  • sliding-window
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Given a string s, return the length of the longest substring (contiguous) that contains no repeating characters.

Input:  s = "abcabcbb"
Output: 3   // "abc"

Input:  s = "bbbbb"
Output: 1   // "b"

Input:  s = "pwwkew"
Output: 3   // "wke"

Mental model: expand a window [left, right]. When you hit a duplicate inside the window, jump left past the previous occurrence.

Brute force

For every start index, grow right until a repeat. Use a set per start.

function lengthOfLongestSubstringBrute(s: string): number {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const seen = new Set<string>();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j])) break;
      seen.add(s[j]);
      best = Math.max(best, j - i + 1);
    }
  }
  return best;
}
Time O(n²)
Space O(min(n, Σ)) charset size

Optimal: sliding window + last index

Keep left as the start of the current unique window. Map each char to its last index. On a hit with index ≥ left, set left = last + 1. Always update best with right - left + 1.

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

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (last.has(ch) && last.get(ch)! >= left) {
      left = last.get(ch)! + 1;
    }
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }

  return best;
}
Time O(n)
Space O(min(n, Σ))

Walk "pwwkew"

right ch left window best
0 p 0 p 1
1 w 0 pw 2
2 w 2 w 2
3 k 2 wk 2
4 e 2 wke 3
5 w 3 kew 3

Edge cases

  • Empty string → 0
  • All unique → s.length
  • All same char → 1
  • Spaces and punctuation count as characters
  • Unicode: JS strings are UTF-16 code units; for full code points use careful iteration if required

Common bugs

  • Moving left only by one when the previous occurrence is far left — you must jump
  • Not checking last.get(ch) >= left (stale indices outside the window)
  • Returning the substring when the problem asks for length (or vice versa)
  • Using a set and forgetting to shrink from the left correctly

Interview delivery

  1. Restate: longest contiguous unique chars.
  2. Brute O(n²), then window.
  3. Code one-pass map.
  4. Trace a string with an internal duplicate.
  5. Complexity O(n) / O(Σ).

Further reading