Longest Substring Without Repeating Characters, Explained

The Problem

You are given a string. Return the length of the longest substring that contains no repeated characters. A substring is a contiguous run of characters, so you cannot skip letters the way you could in a subsequence.

Example 1

Input: s = "abcabcbb"
Output: 3
Why: "abc" is the longest run with all different characters. Every longer run repeats a letter.

Example 2

Input: s = "pwwkew"
Output: 3
Why: "wke" works. "pwke" has the right letters but is not contiguous, so it does not count.

Assumptions to confirm

• Do you want the length or the substring itself? (Usually the length. Returning the substring needs only two extra variables.)
• Which characters can appear: letters only, or spaces, digits and symbols too? (Assume any character; a map handles all of them.)
• Is the comparison case-sensitive? (Assume yes, so "a" and "A" are different.)
• What should an empty string return? (0.)

Start With the Brute Force

The direct answer checks every substring and tests whether its characters are all different. There are about n²/2 substrings, and checking each one can take O(n), so this is O(n³) time. A smarter brute force grows each substring from a fixed start and stops at the first repeat, which brings it to O(n²).

Say this first, then point at the waste: when you find a repeat, you throw away the whole substring and start again one position later, even though almost all of it was valid. A window that keeps the valid part and only drops what it must is the improvement.

The Optimal Approach: A Sliding Window

Solution in Python and TypeScript

Both versions jump the window start directly to the right place instead of moving it one step at a time.

Python

def length_of_longest_substring(s: str) -> int:
    last_seen: dict[str, int] = {}  # char -> latest index
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1  # jump past the repeat
        last_seen[ch] = i
        best = max(best, i - start + 1)
    return best

TypeScript

function lengthOfLongestSubstring(s: string): number {
  const lastSeen = new Map<string, number>(); // char -> latest index
  let start = 0;
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    const prev = lastSeen.get(s[i]);
    if (prev !== undefined && prev >= start) start = prev + 1; // jump past the repeat
    lastSeen.set(s[i], i);
    best = Math.max(best, i - start + 1);
  }
  return best;
}

The check last_seen[ch] >= start is the line most people get wrong. Take "abba": when the final "a" arrives, its last index is 0, but the window already starts at 2 after the second "b". Without the check, start would jump backwards to 1 and the answer would be wrong.

Time and Space Complexity

How to Talk Through Longest Substring Without Repeating Characters in an Interview

A strong spoken answer follows the same five beats:

1. Clarify: "Is it the length or the substring? Any characters, and is it case-sensitive?"
2. Brute force: "I could try every substring, but when I hit a repeat I throw away work I have already done."
3. Optimise: "I will keep a window with no repeats and a map of where I last saw each character. When a repeat lands inside the window, I move the start just past its previous position."
4. Code: narrate the window check and why it compares the last index with start.
5. Test: walk through "abcabcbb", then "abba" for the backwards-jump trap, then the empty string. State O(n) time and O(k) space.

Edge Cases and Common Follow-Ups

Practise Longest Substring Without Repeating Characters in a Mock Coding Round

Reading a solution is not the same as producing one with someone listening. The gap shows up as long silences, a jump straight to code without a brute force, or a bug you only spot after the interviewer asks you to test. The fix is to rehearse problems like Longest Substring Without Repeating Characters out loud, under time pressure, while explaining each decision.

MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).

Frequently Asked Questions