You are given a string s. Return the length of the longest substring that has no repeated character. A substring is a stretch of characters that sit next to each other in the string, with no gaps.
In the last example, "pwke" has no repeats, but it is not an answer. Its letters are not next to each other in s, because the second w sits between p and k. A selection with gaps like that is called a subsequence, not a substring.
The string has up to 50,000 characters. They can be letters, digits, symbols and spaces.
The word contiguous, meaning "next to each other with no gaps", is the clue. Whenever a problem asks for the longest or shortest contiguous stretch that obeys some rule, think of a sliding window.
A sliding window is a stretch of the string marked by two positions, left and right. Both positions only ever move forward. The window follows one rule, and the rule always has the same shape:
Move the right edge forward by one. Always.
While the window breaks the condition, move the left edge forward to repair it.
Once it is repaired, record its size.
Here, the condition is "no character appears twice in the window".
Try every substring, and check each one for repeats.
python
def lengthOfLongestSubstring(s): best = 0 n = len(s) for i in range(n): seen = set() for j in range(i, n): # extend the substring that starts at i if s[j] in seen: break # a repeat: no longer substring from i can work seen.add(s[j]) best = max(best, j - i + 1) return best
This is O(n^2) in the worst case, about 1.25 billion steps for 50,000 characters.
The waste in one sentence: when the substring starting at i hits a repeat, the brute force throws everything away and starts again from i + 1, even though most of the characters it just checked are still fine.
Think of sliding a magnifying glass along a line of letters. The glass grows to the right as long as every letter under it is different. Then a letter arrives on the right that is already under the glass. The glass is now "broken". To fix it, pull the left edge of the glass forward, dropping letters, until the earlier copy of that letter has left. Then keep growing to the right.
We keep the letters under the glass in a hash set, so "is this letter already in the window?" takes constant time.
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: window = set() # (1) left = 0 # (2) best = 0 for right in range(len(s)): # (3) while s[right] in window: # (4) window.remove(s[left]) # (5) left += 1 window.add(s[right]) # (6) best = max(best, right - left + 1) # (7) return best
ts
function lengthOfLongestSubstring(s: string): number { const window = new Set<string>(); // (1) let left = 0; // (2) let best = 0; for (let right = 0; right < s.length; right++) { // (3) while (window.has(s[right])) { // (4) window.delete(s[left]); // (5) left++; } window.add(s[right]); // (6) best = Math.max(best, right - left + 1); // (7) } return best;}
(1) window = set(). The characters currently inside the window. A set lets us check, add and remove a character in constant time.
(2) left = 0. The left edge of the window. The window is everything from left to right, including both ends.
(3) Move the right edge forward, one character per turn. This is step 1 of the window rule.
(4) Is the new character already in the window? If it is, adding it would create a repeat. So before adding, we must repair the window.
(5) Shrink from the left. Remove the leftmost character from the set and move left forward by one. The while loop keeps doing this until the earlier copy of s[right] has been removed. It stops at exactly that point and not a step later.
(6) Add the new character. Now that the window has no copy of it, adding it is safe.
(7) Record the window's size.right - left + 1 is the number of characters from left to right, counting both ends. The + 1 is there because both ends are included. A window from position 2 to position 4 holds three characters: 2, 3 and 4.
Time. There is a while loop inside a for loop, so it looks like O(n^2). It is not. Count the total work instead of the work per turn.
right moves forward exactly n times in total, once per turn of the for loop.
left only moves forward, and it can never pass right. So across the whole run, left moves forward at most n times in total. It is not n times per turn.
Each move of either pointer does a constant amount of set work.
So the total is at most n + n = 2n moves, which is O(n). This is the same "count the total, not the per-turn work" argument as 4.4.9.
Space. The set holds the distinct characters in the window. That is at most the number of different characters in the alphabet, call it k. So the space is O(k). If the alphabet has a fixed size, like the 95 printable characters, that is O(1).
Instead of moving left one step at a time, remember where each character was last seen. When a repeat arrives, jump left straight past the earlier copy.
python
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: last_seen = {} # (1) left = 0 best = 0 for right, c in enumerate(s): if c in last_seen and last_seen[c] >= left: # (2) left = last_seen[c] + 1 # (3) last_seen[c] = right # (4) best = max(best, right - left + 1) return best
(1) A map from each character to the last position where it appeared.
(2) Is this character a repeat inside the current window? The second half of the check, last_seen[c] >= left, is easy to forget and it is essential. The map remembers every character ever seen, including ones that have already slid out of the window on the left. Those old positions must be ignored.
(3) Jump left to one past the earlier copy, so the earlier copy is now outside the window.
(4) Record where this character was seen, for next time.
Here is what goes wrong without the >= left check. Take "abba".
At right = 2, the second b arrives. The first b was at 1, so left jumps to 2.
At right = 3, the second a arrives. The map says a was last seen at 0.
Without the check, left jumps to 0 + 1 = 1. That moves leftbackwards, from 2 to 1.
The window is now "bba", which contains a repeat, and the answer comes out wrong.
With the check, last_seen['a'] is 0, which is less than left = 2, so we ignore it. Both versions are O(n). This one does fewer steps, and the check is the price.
The same skeleton solves a family. Only the condition in line (4) changes.
At most k different characters. Use a map of counts instead of a set, and shrink while the map has more than k keys.
Exactly k different characters. Count the windows with "at most k" and subtract those with "at most k − 1". This trick turns a hard "exactly" rule into two easy "at most" rules.
Longest Repeating Character Replacement. Shrink while the number of characters you would need to change is more than k. That is the next page, 4.6.3.
Minimum Window Substring. Find the shortest window instead of the longest. That changes where you record the answer. See 4.6.5.
"Why is this O(n) and not O(n^2)?"left only moves forward and never passes right, so it moves at most n times in total.
"Substring or subsequence?" Substring, meaning no gaps. Say this back to the interviewer before coding. It is a real ambiguity in some wordings, and checking costs five seconds.
"What if you had to return the substring itself?" Whenever you update best, also save left. At the end, slice from that left for best characters.
"What if the string can contain any Unicode character?" The set and map still work. Only a fixed-size array version would break.
One thing to volunteer: say the window rule before you write it. "Move right always. Shrink left while the window breaks the rule. Record after repairing." Every problem in this chapter is that sentence with a different rule.