Longest Substring Without Repeating Characters
Find the length of the longest substring with no repeated character using a variable-size sliding window and a map, in O(n) time.
Updated Short read: 4 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(k) |
| Sliding window with last-seen map | O(n) | O(k) |
The problem
Given a string, return the length of the longest substring in which no character appears twice. A substring is a run of consecutive characters.
"abcabcbb" → 3 ("abc")
"bbbbb" → 1 ("b")
"pwwkew" → 3 ("wke")
"" → 0In the third example "pwke" is not a valid answer: its characters are not consecutive in the original string.
In the complexity figures, n is the length of the string and k is the number of different characters in it.
Approach 1: brute force
From each starting position, extend to the right until a character repeats.
JavaScript
function lengthOfLongestSubstringBruteForce(text) {
let best = 0;
for (let start = 0; start < text.length; start++) {
const seen = new Set();
for (let end = start; end < text.length; end++) {
if (seen.has(text[end])) break;
seen.add(text[end]);
best = Math.max(best, end - start + 1);
}
}
return best;
}Python
def length_of_longest_substring_brute_force(text):
best = 0
for start in range(len(text)):
seen = set()
for end in range(start, len(text)):
if text[end] in seen:
break
seen.add(text[end])
best = max(best, end - start + 1)
return bestTime O(n²) in the worst case. Space O(k) for the set.
Approach 2: sliding window
The brute force throws away everything it learned each time it moves to a new start. A sliding window keeps it.
Hold a window from start to end that never contains a repeat. Move end one character at a time. If the new character is already inside the window, the window is no longer valid, and the fix is to move start to just past the earlier copy of that character.
To do that without searching, keep a map from each character to the index where it was last seen.
JavaScript
function lengthOfLongestSubstring(text) {
const lastSeen = new Map();
let start = 0;
let best = 0;
for (let end = 0; end < text.length; end++) {
const ch = text[end];
if (lastSeen.has(ch) && lastSeen.get(ch) >= start) {
start = lastSeen.get(ch) + 1;
}
lastSeen.set(ch, end);
best = Math.max(best, end - start + 1);
}
return best;
}Python
def length_of_longest_substring(text):
last_seen = {}
start = 0
best = 0
for end, ch in enumerate(text):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1
last_seen[ch] = end
best = max(best, end - start + 1)
return bestWalkthrough
"abba":
| end | Character | Last seen at | Action | Window | best |
|---|---|---|---|---|---|
| 0 | a | never | Extend | "a" | 1 |
| 1 | b | never | Extend | "ab" | 2 |
| 2 | b | 1, inside the window | start = 2 | "b" | 2 |
| 3 | a | 0, before the window | Extend | "ba" | 2 |
Time O(n): one pass, with constant-time map operations. Space O(k).
Why the check includes >= start
The map remembers every character ever seen, including ones the window has already moved past. In the last row above, a was last seen at index 0, but the window starts at index 2, so that old a is no longer in it and is not a repeat.
Without the >= start condition, the code would set start back to 1. The window would then be "bba", which contains a repeat, and the function would return 3 instead of 2. start must never move backwards.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("abba")); // 2Python
print(length_of_longest_substring("abcabcbb")) # 3
print(length_of_longest_substring("abba")) # 2The comment after each line is the result you should see.
Common mistakes
- Leaving out the
>= startcheck."abba"is the standard test for this bug. - Getting the window length wrong. It is
end - start + 1, because both ends are included. - Updating
bestonly when a repeat is found. The longest window may be the one that reaches the end of the string, so update on every step.
Original problem: LeetCode 3: Longest Substring Without Repeating Characters