Longest Substring Without Repeating Characters

medium

hash-tablestringsliding-window

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

A substring is a run of consecutive characters from s (not a subsequence). The answer is a single number — the length of the longest such run — not the substring itself.

Example

Input: s = "abcabcbb"

Output: 3

The longest run without a repeat is abc, length 3.

Constraints

0 <= s.length <= 5 * 10^4
s consists of English letters, digits, symbols, and spaces.

Intuition

The most direct approach takes every substring and checks whether it has a repeated character, keeping the length of the longest one that doesn't. Comparing a substring against itself for uniqueness is what makes it slow.

function lengthOfLongestSubstring(s) {
  // A substring has no repeat when its set of chars is as big as the substring.
  const allUnique = (str) => new Set(str).size === str.length;
  let best = 0;
  // Try every substring s[i..j] and keep the longest distinct one.
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (allUnique(s.slice(i, j + 1))) best = Math.max(best, j - i + 1);
    }
  }
  return best;
}

Brute force — test every substring for uniqueness: O(n³).

This is O(n³) — there are O(n²) substrings and each uniqueness check is O(n). Can we do better?

The key observation: as we extend a substring to the right, it stays valid until the first repeated character. Once a duplicate appears, every substring that keeps the earlier copy is also invalid — so instead of restarting, we can just move the left edge past that earlier copy. That's a sliding window: a window [start, i] that always holds distinct characters.

To know where the earlier copy was, store each character's most recent index in a map. When s[i] was last seen at some index >= start, that copy is inside the window, so jump start to one past it. The answer is the widest i - start + 1 seen.

(The walkthrough below frames the window as `left`/`right`; in the stored solution `right` is the loop index `i` and `left` is `start` — same window, different names.)

Walking it through:

s = "abcabcbb" — window [start, i], start jumps past the last duplicate

left↓

right↓

best = 3

Window "abc" — all distinct. lastSeen = {a:0, b:1, c:2}.

left↓

right↓

"a" last seen at 0 ≥ start → start = 1

right = 3 is "a", whose last index 0 sits in the window — jump start past it to 1.

left↓

right↓

"b" last seen at 1 ≥ start → start = 2

right = 4 is "b" (last at 1, in-window) → start jumps to 2. Window "cab", still width 3.

left↓right↓

"b" last seen at 4 ≥ start → start = 6

right = 6 is "b" again (last at 4) → start leaps to 6. The window collapses to one char.

left↓right↓

"b" last seen at 6 ≥ start → start = 7

The trailing run of b's keeps width at 1. Nothing beat the early "abc". Final best = 3.

Optimization

Sliding window with last-seen map

Keep a window [start, i] that holds only distinct characters. Walk i over the string, tracking the most recent index of each character in a map. When the current character was last seen at or after start, the window now contains a duplicate, so jump start to one past that last occurrence. The best length is the largest i - start + 1 seen.

Each character is visited once and start only moves forward, so it's O(n) time and O(min(n, alphabet)) space.

function lengthOfLongestSubstring(s) {
  // lastSeen[ch] = the most recent index where ch appeared.
  const lastSeen = new Map();
  let start = 0; // left edge of the window of distinct characters
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    // If ch's last copy is inside the window, jump start past it so the window stays distinct.
    if (lastSeen.has(ch) && lastSeen.get(ch) >= start) {
      start = lastSeen.get(ch) + 1;
    }
    lastSeen.set(ch, i);
    best = Math.max(best, i - start + 1); // width of the current valid window
  }
  return best;
}

Complexity analysis

Time complexity: O(n). Here's why:

The loop visits each index i once, left to right.
Per step the work is O(1): one map lookup, one map write, and a constant comparison — start only ever moves forward, so it isn't a nested scan.

The whole pass is O(n), where n is the length of s — versus the O(n³) of the brute force.

Space complexity: O(min(n, σ)). Here's why:

The lastSeen map holds at most one entry per distinct character.
That can't exceed the alphabet size σ, nor the string length n.

So the extra space is O(min(n, σ)) — bounded by the alphabet for a fixed character set.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
s = ""	0	Empty string — the loop never runs.
s = "z"	1	Single character — window of width 1.
s = "bbbb"	1	All identical — start keeps jumping, width stays 1.
s = "abcde"	5	All distinct — the whole string is the window.
s = "abccba"	3	start must not rewind: after the "cc" repeat the leading "ab" sits outside the window.
s = "tmmzuxt"	5	Answer "mzuxt" is in the middle; the early "t" is correctly skipped.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor