vizlearn

Longest substring without repeating characters

Interview QuestionsBy Updated

A sliding window with a dictionary of last-seen positions. Extend the right edge one character at a time; when a character repeats inside the current window, jump the left edge past its previous occurrence. Every character is visited once, so it is O(n).

Overview

Why brute force is quadratic

Checking every substring is O(n²) substrings, each needing a uniqueness test — O(n³) naively, O(n²) with a set per start. The waste is that each restart throws away everything the previous one learned.

The window keeps it. When the right edge advances, the answer for the new window is derived from the old one instead of recomputed.

StringsCoding problemMedium

Step through it

What to watch

  • The right edge never goes backwards — that is what keeps it linear.
  • On a repeat, the left edge jumps rather than creeping.
  • A repeat that already fell off the left is ignored — watch abba.

Say this out loud

"Sliding window with a last-seen map. Right edge always advances; on a repeat inside the window the left edge jumps past the old occurrence. O(n) time, O(k) space in the alphabet."

Longest substring without repeating characters

Find the length of the longest substring with no repeated character.

The jump, and the guard

Store each character's last index. When the character at the right edge has been seen, the left edge moves to seen[ch] + 1 — one past the previous occurrence, in a single step.

The guard is the subtle part: only jump if seen[ch] >= start. Without it, a character last seen before the current window drags the left edge backwards, shrinking the window for no reason. "abba" is the shortest input that exposes it: at the final a, the earlier a is already outside the window.

Cost, and what to say about space

Time is O(n): the right edge advances n times and the left edge only ever moves forwards, so both pointers together make at most 2n moves. Space is O(k) in the size of the alphabet, not O(n) — the map holds one entry per distinct character.

Interviewers like the space answer because most candidates say O(n).

Run it in Python

The window printed at every step, then the same input run against brute force so the operation counts sit side by side, and finally the abba case with the guard removed.

longest_unique.pyPython 3
Output
How the code works
  1. if ch in seen and seen[ch] >= start:The guard. A repeat only matters while it is inside the window; an older occurrence has already fallen off the left edge and must be ignored.
  2. start = seen[ch] + 1One jump instead of walking the left edge forward one character at a time. Both are correct; this one keeps the whole scan clearly linear.
  3. seen[ch] = iStoring the index rather than a count is what makes the jump possible. A count-based window works too and needs the left edge to walk.
  4. i - start + 1The window length. Off-by-one here is the most common way to get an answer that is right on most inputs and wrong on the edges.
Change one thing
  • Run "abba" through both. The guard is the entire difference between 2 and 3.
  • Return the substring rather than the length by tracking start at the moment best improves — the usual follow-up.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why is `seen[ch] >= start` needed as well as `ch in seen`?
  2. The time complexity is O(n) because:
  3. The space complexity is:





 Cheat sheet
Longest substring without repeating characters
A sliding window with a dictionary of last-seen positions. Extend the right edge one character at a time; when a character repeats inside the current window, jump the left edge past its previous occurrence. Every character is visited once, so it is O(n).
INTERVIEW · vizlearn.in/interview/longest-substring-without-repeating-characters.html
More in Interview
InterviewFirst non-repeating characterInterviewValid parenthesesInterviewRun-length string compressionInterviewLongest common prefix
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact