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)
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".
- a0
- b1
- c2
- a3
- b4
- c5
- b6
- b7
The rules that matter:
- Return the length, not the substring itself.
- The characters must be next to each other.
scan contain letters, digits, symbols and spaces, and can be empty (answer 0).
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).
- a0
- b1
- c2
- a3
- b4
Pause and think
left moves past the first a only: from index 0 to index 1. The window
becomes "bca" (indexes 1 to 3), length 3. We don’t need to throw away b or
c, because they don’t repeat.
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"
- p0
- w1
- w2
- k3
- e4
- w5
- empty
- 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.
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 bestEvery 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.
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
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”
- Start with an empty set
inWindow,left = 0andbest = 0. - Move
rightfrom the first character to the last. - While
s[right]is already in the set, removes[left]from the set and moveleftone step right (shrink). - Add
s[right]to the set (grow). - The window now runs from
lefttoright; its length isright − 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"
- a0
- b1
- c2
- a3
- b4
- c5
- b6
- b7
- empty
- 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.
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.
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"
- a0
- b1
- c2
- a3
- b4
- c5
- b6
- b7
| char | last index | |
|---|---|---|
| empty | ||
- 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.
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 bestThe 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.
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 bestOn 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:
leftis the back of the window;bestis 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
leftforward. This repeats until the old copy ofs[right]is gone, because the old copy isn’t always the leftmost character: in"abcb", adding the secondbmeans droppingaand then the firstb. - Line 10 (JS) / line 9 (Python): now it’s safe, so add the new character.
- Line 11 (JS) / line 10 (Python): the window from
lefttorighthasright − left + 1characters (both ends count). Keep the biggest. - The last line: return the best length.
s = "abcabcbb" with the set version:
| right | s[right] | repeat? | dropped from the left | window after | length | best |
|---|---|---|---|---|---|---|
| 0 | a | no | — | a | 1 | 1 |
| 1 | b | no | — | ab | 2 | 2 |
| 2 | c | no | — | abc | 3 | 3 |
| 3 | a | yes | a | bca | 3 | 3 |
| 4 | b | yes | b | cab | 3 | 3 |
| 5 | c | yes | c | abc | 3 | 3 |
| 6 | b | yes | a, b | cb | 2 | 3 |
| 7 | b | yes | c, b | b | 1 | 3 |
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.
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.
What to say out loud:
- “Substring means the characters are next to each other, so this is a sliding window.”
- “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.”
- “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).”
- “Each character enters and leaves the window at most once, so it’s O(n).”
- Offer the last-seen map as an improvement, and mention the
abbatrap.
Likely follow-up questions:
- “Can you return the substring itself?” Remember
leftandrightwheneverbestimproves, 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:
- Longest Repeating Character Replacement: the same grow/shrink window, with letter counts instead of a set.
- Permutation in String: a window of a fixed size.
- Best Time to Buy and Sell Stock: a single pass whose left edge jumps forward.