How do you find the longest substring without repeating characters?

Q: How do you find the longest substring without repeating characters?

**Target Audience:** Beginners preparing for coding interviews — you should know strings, loops and what a map is. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged `📌 Interview term:` with the exact vocabulary an interviewer expects. Every output quoted in the **Verified** section was printed by actually running the code shown with `python3`. ## 1. Why This Even Matters — A Story First You are reading a long necklace of coloured beads through a magnifying glass, and you want the longest stretch where **no colour repeats**. You slide the glass to the right one bead at a time. The moment a colour shows up that is already under the glass, you do not start over — you just slide the **left edge** of the glass past the earlier bead of that colour, and keep going. The glass only ever moves forward, on both edges. That magnifying glass is a **sliding window**, and this problem is the textbook example of

The problem

Question presented to candidate: "Given a string, find the length of the longest substring that has no repeating characters. For example, for 'abcabcbb' the answer is 3, for 'abc'. Please write it in Python and walk me through its complexity."

What a strong answer should cover:

Brute force over all substrings is O(n²) to O(n³); the expected answer is a variable-size sliding window in O(n).
A last-seen index map so left can jump past the earlier copy, and why the jump must be max(left, last + 1) (stale indices, the "abba" case).
The window invariant: no repeats inside s[left..right], left never decreases; window length is right - left + 1.
Space O(min(n, k)) for alphabet size k, and the set-based alternative that shrinks one step at a time.
Python specifics: a dict as the last-seen map (or a set for the shrinking variant), enumerate for index and character together, and the fact that Python strings index by Unicode code point, so an emoji counts as one character.

Clarifying questions expected:

"What is the character set — ASCII, lowercase only, or Unicode?"
"Do you want the length or the substring itself?"

Code / implementation expected: Yes — a longest_unique(s) function in Python returning the length (and optionally the substring).

strings
sliding-window

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know strings, loops and what a map is. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged 📌 Interview term: with the exact vocabulary an interviewer expects. Every output quoted in the Verified section was printed by actually running the code shown with python3.

1. Why This Even Matters — A Story First

You are reading a long necklace of coloured beads through a magnifying glass, and you want the longest stretch where no colour repeats. You slide the glass to the right one bead at a time. The moment a colour shows up that is already under the glass, you do not start over — you just slide the left edge of the glass past the earlier bead of that colour, and keep going. The glass only ever moves forward, on both

The solution is hidden so you can try first

9 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonSliding window with last-seen indices on eight inputs

Practice

PythonWhy max(left, last + 1): trace and buggy vs fixed vs set

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.