Skip to content
16-Week DSA Roadmap
LeetCode #3MediumProblem 6 of 8

Longest Substring Without Repeating Characters

Find the length of the longest stretch of a string in which no character appears twice.

  • Variable-size sliding window
  • Hash set membership

Before this, know: Strings and indexes, Hash sets and hash maps (week 1)

The problem in plain English

You get a string s. A substring is a run of characters that sit next to each other in s: in "pwwkew", "wke" is a substring but "pwke" is not (it skips a letter).

Find the length of the longest substring in which no character repeats.

Example: s = "abcabcbb".

s
  1. a0
  2. b1
  3. c2
  4. a3
  5. b4
  6. c5
  7. b6
  8. b7
'abc' (indexes 0 to 2) has no repeats and length 3. Any longer stretch, like 'abca', contains a character twice. Answer: 3.

The rules that matter:

  • Return the length, not the substring itself.
  • The characters must be next to each other.
  • s can contain letters, digits, symbols and spaces, and can be empty (answer 0).

Before you code: think it through

The caterpillar is a sliding window: a stretch of the string between two pointers, left (the back) and right (the front). The window grows on the right and shrinks on the left. To check “is this letter already inside?” in one step, we keep the window’s letters in a hash set (a collection that answers “is X in here?” instantly, from week 1).

  1. a0
  2. b1
  3. c2
  4. a3
  5. b4
The window 'abc' (shaded) is valid. right now reaches another 'a', which is already inside, so the window has to shrink from the left before it can take it.

Pause and think

In the picture, the window is 'abc' and right is on the second 'a'. How far must left move before we can add that 'a'? What's the window then?

Approach 1: Brute force

From every starting index, extend the end one character at a time, remembering the characters in a set, until we hit a repeat. Keep the longest run found.

Brute force: every start

s = "pwwkew"

s
  1. p0
  2. w1
  3. w2
  4. k3
  5. e4
  6. w5
seen0 items
    empty
variables
window length
—
best
0
  • Inside the window
  • Character being added
  • Repeat!
  • Just dropped
  • Left behind
  • Longest window

Try every starting index. From each start, extend the end one character at a time until we hit a repeat.

Step 1 / 17

Which line is running?

function lengthOfLongestSubstring(s) {  let best = 0;Running now:   for (let start = 0; start < s.length; start++) {    const seen = new Set();    for (let end = start; end < s.length; end++) {      if (seen.has(s[end])) break; // a repeat: this start can't go further      seen.add(s[end]);      best = Math.max(best, end - start + 1);    }  }  return best;}

Brute force

function lengthOfLongestSubstring(s) {  let best = 0;  for (let start = 0; start < s.length; start++) {    const seen = new Set();    for (let end = start; end < s.length; end++) {      if (seen.has(s[end])) break; // a repeat: this start can't go further      seen.add(s[end]);      best = Math.max(best, end - start + 1);    }  }  return best;}
def length_of_longest_substring(s):    best = 0    for start in range(len(s)):        seen = set()        for end in range(start, len(s)):            if s[end] in seen:                break  # a repeat: this start can't go further            seen.add(s[end])            best = max(best, end - start + 1)    return best

Why is it slow?

Every time we hit a repeat, we start over from the next index and re-read characters we’ve already checked. With "pwwkew" that’s 15 checks for 6 characters.

How far can one start scan? Call k the number of different characters the string can contain (LeetCode allows letters, digits, symbols and spaces: at most 95). After k + 1 characters, some character must have repeated, so each start reads at most k + 1 characters. With n starts, that’s at most about n × k steps.

We describe this growth with Big-O notation, a short way of saying how the work grows as the input grows (see Big-O in 5 minutes). Here it’s O(n · k): each of the n starts may re-read up to k characters that the previous start already checked. If any character at all were allowed (so k could be as big as n), it would be O(n²): double the string, four times the work. The sliding window below reads each character a fixed number of times, whatever k is.

The pattern: variable-size sliding window

Nothing is re-read: right visits each character once, and left also only moves forward, so each character enters the window once and leaves at most once.

Pattern

Variable-size sliding window

Template

Use it when: you want the longest (or shortest) run of neighbouring items that satisfies a rule, and adding items can only break the rule while removing them can only fix it.

Signal words

  • “longest substring”
  • “contiguous”
  • “without repeating”
  • “at most”
  • “subarray”

Approach 2: Sliding window with a set

  1. Start with an empty set inWindow, left = 0 and best = 0.
  2. Move right from the first character to the last.
  3. While s[right] is already in the set, remove s[left] from the set and move left one step right (shrink).
  4. Add s[right] to the set (grow).
  5. The window now runs from left to right; its length is right − left + 1. Keep the biggest.

The shaded boxes are the window. Watch the window grow on the right, and when a red repeat shows up, shrink one character at a time on the left until the old copy is gone. The set below always holds exactly the window’s characters.

Sliding window with a set

s = "abcabcbb"

s
  1. a0
  2. b1
  3. c2
  4. a3
  5. b4
  6. c5
  7. b6
  8. b7
inWindow0 items
    empty
variables
window length
—
best
0
  • Inside the window
  • Character being added
  • Repeat!
  • Just dropped
  • Left behind
  • Longest window

The window is the stretch of characters between left and right. Its rule: no character twice. A set ("inWindow") remembers which characters are inside, so checking takes one step.

Step 1 / 22

Which line is running?

function lengthOfLongestSubstring(s) {Running now:   const inWindow = new Set(); // characters currently inside the window  let left = 0;  let best = 0;  for (let right = 0; right < s.length; right++) {    while (inWindow.has(s[right])) {      inWindow.delete(s[left]); // shrink: drop the leftmost character      left++;    }    inWindow.add(s[right]); // grow: take in the new character    best = Math.max(best, right - left + 1);  }  return best;}

Try bbbbb: every new b pushes the old one out, so the window never gets longer than 1. And empty: the loop never runs, and the answer is 0.

Approach 3: Jump with a last-seen map

Shrinking one step at a time is already fast, but we can do even better: if we remember the last index where we saw each character in a hash map, we can move left straight past the old copy in one jump.

Sliding window with a last-seen map

s = "abcabcbb"

s
  1. a0
  2. b1
  3. c2
  4. a3
  5. b4
  6. c5
  7. b6
  8. b7
lastSeen0 items
charlast index
empty
variables
window length
—
best
0
  • Inside the window
  • Character being added
  • Repeat!
  • Just dropped
  • Left behind
  • Longest window

This time a map remembers, for every character, the LAST index where we saw it. When we hit a repeat, we can jump left straight past the old copy instead of shrinking one step at a time.

Step 1 / 23

Which line is running?

function lengthOfLongestSubstring(s) {Running now:   const lastSeen = new Map(); // character -> the last index where we saw it  let left = 0;  let best = 0;  for (let right = 0; right < s.length; right++) {    const ch = s[right];    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {      left = lastSeen.get(ch) + 1; // jump just past the earlier copy    }    lastSeen.set(ch, right);    best = Math.max(best, right - left + 1);  }  return best;}

Last-seen map

function lengthOfLongestSubstring(s) {  const lastSeen = new Map(); // character -> the last index where we saw it  let left = 0;  let best = 0;  for (let right = 0; right < s.length; right++) {    const ch = s[right];    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {      left = lastSeen.get(ch) + 1; // jump just past the earlier copy    }    lastSeen.set(ch, right);    best = Math.max(best, right - left + 1);  }  return best;}
def length_of_longest_substring(s):    last_seen = {}  # character -> the last index where we saw it    left = 0    best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump just past the earlier copy        last_seen[ch] = right        best = max(best, right - left + 1)    return best

The check lastSeen.get(ch) >= left matters. Try the abba example: when we reach the final a, the map says a was last seen at index 0, but left is already at 2. That old a is outside the window, so it isn’t a repeat, and left must not jump backwards to 1.

Both approaches are O(n). The jump version does fewer steps; the set version is the classic template and easier to get right under pressure. Either is a great interview answer.

The code, line by line

Here is Approach 2 again, the one to learn first:

Sliding window with a set

function lengthOfLongestSubstring(s) {  const inWindow = new Set(); // characters currently inside the window  let left = 0;  let best = 0;  for (let right = 0; right < s.length; right++) {    while (inWindow.has(s[right])) {      inWindow.delete(s[left]); // shrink: drop the leftmost character      left++;    }    inWindow.add(s[right]); // grow: take in the new character    best = Math.max(best, right - left + 1);  }  return best;}
def length_of_longest_substring(s):    in_window = set()  # characters currently inside the window    left = 0    best = 0    for right in range(len(s)):        while s[right] in in_window:            in_window.remove(s[left])  # shrink: drop the leftmost character            left += 1        in_window.add(s[right])  # grow: take in the new character        best = max(best, right - left + 1)    return best

On LeetCode it’s var lengthOfLongestSubstring = function(s) in JavaScript, and def lengthOfLongestSubstring(self, s) inside class Solution in Python.

  • Line 2: the set of characters inside the window. new Set() in JavaScript, set() in Python. Adding, removing and checking each take about one step.
  • Lines 3–4: left is the back of the window; best is the longest valid window seen so far.
  • Line 5: right, the front of the window, visits every index once.
  • Line 6: is the new character already inside? If so, we can’t add it yet.
  • Lines 7–8: drop the leftmost character from the set and move left forward. This repeats until the old copy of s[right] is gone, because the old copy isn’t always the leftmost character: in "abcb", adding the second b means dropping a and then the first b.
  • Line 10 (JS) / line 9 (Python): now it’s safe, so add the new character.
  • Line 11 (JS) / line 10 (Python): the window from left to right has right − left + 1 characters (both ends count). Keep the biggest.
  • The last line: return the best length.

Dry run

s = "abcabcbb" with the set version:

rights[right]repeat?dropped from the leftwindow afterlengthbest
0ano—a11
1bno—ab22
2cno—abc33
3ayesabca33
4byesbcab33
5cyescabc33
6byesa, bcb23
7byesc, bb13
s = "abcabcbb"

The right = 6 row shows why the shrink is a while, not an if: the old b was the second character of the window, so we had to drop a first.

Complexity

Brute force

Time

O(n · k)

Each of the n starts stops at the first repeat, so it reads at most k + 1 characters (k = how many different characters are possible). If k could grow as big as n, that's O(n²).

Space

O(k)

The set holds at most k characters, where k is the number of different characters possible (at most 95 printable ones, often written as O(1)).

Sliding window with a set

Time

O(n)

right moves n times; left also moves at most n times in total. So at most 2n steps: double the string, double the work.

Space

O(k)

The set never holds more different characters than exist (k), however long the string is.

Last-seen map

Time

O(n)

right moves n times and left jumps, never stepping one by one: exactly n rounds of the loop.

Space

O(k)

One map entry per different character.

The “2n steps” argument is the key idea of every sliding window: even though there’s a loop inside a loop, left never moves backwards, so the inner loop runs at most n times in total, not n times per character.

Common mistakes and edge cases

What to say out loud:

  1. “Substring means the characters are next to each other, so this is a sliding window.”
  2. “Brute force restarts from every index and re-reads up to k characters each time: O(n · k), or O(n²) if any character is allowed.”
  3. “I’ll keep a window with no repeats. Grow on the right; on a repeat, shrink from the left until it’s gone. A set makes the check O(1).”
  4. “Each character enters and leaves the window at most once, so it’s O(n).”
  5. Offer the last-seen map as an improvement, and mention the abba trap.

Likely follow-up questions:

  • “Can you return the substring itself?” Remember left and right whenever best improves, then slice.
  • “At most two different characters instead of no repeats?” Same window; the rule changes to “the count map has at most 2 keys”. That’s the next pattern: window with counts.

Related problems: