Find the length of the longest substring with no repeated characters using a sliding window and last-seen index map in O(n). A top interview question.
The problem
Return the length of the longest substring of s that contains no repeated characters.
For "abcabcbb" the answer is 3 ("abc").
Examples
Example 1
Input
longest_unique_substring('abcabcbb')Expected output
3
Example 2
Input
longest_unique_substring('bbbbb')Expected output
1
Example 3
Input
longest_unique_substring('pwwkew')Expected output
3
+ 4 hidden tests on Submit — start must never move backwards.
Edge cases to ask about
- Empty string
- All the same character
- 'abba' (stale index)
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Every start, extend until a repeat | O(n·k) | O(k) | Restarts from scratch at every index. |
| bestSliding window + last-seen map | O(n) | O(k) | When a repeat appears inside the window, jump the start past its previous position. |
Walkthrough of the optimal approach (try it yourself first)
Maintain a window s[start : i+1] with no repeats and a dict of each character's last index.
When s[i] was last seen at or after start, the window would contain it twice, so jump start to one past that position. Record last[ch] = i and update the best length.
The last[ch] >= start check is the subtle part: in "abba", the final a was last seen before the window, so start must not jump backwards.
Complexity: O(n) time, O(k) space. Each index enters the window once and the start pointer only moves forward; the map has one entry per distinct character.
Reveal the reference solution
def longest_unique_substring(s): last = {} start = best = 0 for i, ch in enumerate(s): if ch in last and last[ch] >= start: start = last[ch] + 1 last[ch] = i best = max(best, i - start + 1) return best
The brute force, for comparison
def longest_unique_substring(s): best = 0 for i in range(len(s)): seen = set() for j in range(i, len(s)): if s[j] in seen: break seen.add(s[j]) best = max(best, j - i + 1) return best
Follow-ups interviewers ask
- Return the substring itself.
- At most k distinct characters.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Longest Substring Without Repeating Chars in Python?
The optimal solution runs in O(n) time and O(k) auxiliary space. Each index enters the window once and the start pointer only moves forward; the map has one entry per distinct character.
What is the brute-force approach, and how do you optimise it?
Every start, extend until a repeat: O(n·k) time, O(k) space. Restarts from scratch at every index. Sliding window + last-seen map: O(n) time, O(k) space. When a repeat appears inside the window, jump the start past its previous position.
What follow-up questions do interviewers ask about Longest Substring Without Repeating Chars?
Return the substring itself. At most k distinct characters.