Longest Substring Without Repeating Characters
Learn the sliding window technique for the longest substring without repeating characters and how to answer this interview question.
Expected Interview Answer
The longest substring without repeating characters is found with a sliding window and a hash map that stores the last seen index of each character: expand the right pointer through the string, and whenever a repeat is found inside the current window, jump the left pointer directly past the repeat's previous position, tracking the maximum window length throughout in a single O(n) pass.
As the right pointer visits each character, you check whether that character's last recorded index is inside the current window; if it is, you move the left pointer to one past that recorded index rather than incrementing it one step at a time, which avoids redundant work. You then update the character's last-seen index to the current right position and compare the current window length (right minus left plus one) against the running maximum. Because the left pointer only ever jumps forward and the right pointer only ever advances, the total work across the whole scan is O(n) time and O(min(n, alphabet size)) space for the hash map. The key insight interviewers listen for is that you don't need to shrink the window character by character — a direct jump using the stored index is what turns a naive O(n^2) approach into a single linear pass.
- O(n) time with a single pass using last-seen indices
- O(min(n, alphabet size)) space for the index map
- Left pointer jumps directly to the right spot instead of stepping one at a time
- Generalizes to "longest substring with at most k distinct characters" variants
AI Mentor Explanation
A net-session organizer tracking the longest stretch of overs where no bowler repeats keeps a note of each bowler's most recent over number. When a bowler is about to be scheduled again inside the current active stretch, the organizer doesn't remove bowlers one at a time from the front — they jump the start of the stretch directly to just after that bowler's last recorded over. The bowler's most recent over number is then updated to now, and the organizer compares the current stretch length against the longest seen so far. This direct jump, rather than a step-by-step trim, is what keeps scheduling the whole session's overs a single fast pass.
Step-by-Step Explanation
Step 1
Initialize tracking structures
Use a hash map for last-seen index of each character, left pointer at 0, and a max-length variable at 0.
Step 2
Advance the right pointer
For each character, check if it exists in the map with an index >= left (inside the current window).
Step 3
Jump left on repeat
If the character was last seen inside the window, set left to one past that last-seen index instead of incrementing step by step.
Step 4
Update and compare
Record the character's new last-seen index as right, then update the max length using right - left + 1.
What Interviewer Expects
- Explain why brute force checking every substring is O(n^3) or O(n^2)
- Justify why jumping left directly (not incrementally) keeps the pass linear
- Correctly guard against jumping left backward if the stored index is stale (before the current left)
- State final complexity as O(n) time, O(min(n, alphabet)) space
Common Mistakes
- Incrementing left one step at a time on every repeat instead of jumping directly, causing quadratic behavior
- Forgetting to check that the last-seen index is still inside the current window before jumping left
- Not updating the last-seen index after handling a repeat, causing stale jumps later
- Confusing this with the "at most k distinct characters" variant, which needs a frequency count instead of last-seen index
Best Answer (HR Friendly)
“I slide a window across the string while remembering the last position I saw each character. If I see a character again inside my current window, I jump the start of my window straight past where I last saw it, instead of nudging forward one character at a time. That single jump is what keeps the whole scan linear, and I just track the longest window length as I go.”
Code Example
def length_of_longest_substring(s):
last_seen = {}
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
last_seen[ch] = right
best = max(best, right - left + 1)
return bestFollow-up Questions
- How would you return the actual substring instead of just its length?
- How would you solve the variant with at most k distinct characters?
- How would you handle Unicode characters where a simple array index by ASCII code will not work?
- How would you adapt this to run over a stream where you cannot store the whole string?
MCQ Practice
1. What data structure powers the linear-time solution?
Storing each character's most recent index lets the left pointer jump directly past a repeat instead of scanning.
2. Why must you check that the stored last-seen index is >= left before jumping?
A character might have appeared earlier but already fallen out of the current window; jumping on a stale index would move left backward, breaking correctness.
3. What is the time complexity of this sliding window approach?
Both pointers move forward monotonically across the string, giving a single O(n) pass.
Flash Cards
What does the hash map store in this problem? — The most recent index at which each character was seen.
What happens when a repeated character is found inside the window? — The left pointer jumps directly to one past the character's last recorded index.
What is the time complexity? — O(n), a single linear pass with the right pointer.
What guard prevents an incorrect backward jump? — Checking that the last-seen index is still >= the current left pointer before jumping.