LeetCode 3: Longest Substring Without Repeating Characters, Fully Explained

LeetCode 3 is usually the first sliding window problem people meet, and it's still one of the most commonly reported questions in phone screens and first coding rounds. The basic solution fits in ten lines. What separates candidates is whether they can explain why the window is O(n), handle the one edge case that breaks the index-map version, and adapt the same skeleton when the interviewer changes "no repeats" to "at most K distinct".

This page walks through all of that: brute force, the set-based window, the index-jump optimisation, two full dry runs, code in Python, C++ and Java, and the follow-ups. If you want the general pattern first, the sliding window technique guide covers the three templates this problem belongs to.

The Problem: Longest Substring Without Repeating Characters

Given a string s, return the length of the longest substring that contains no repeated character.

Constraints on LeetCode: 0 ≤ s.length ≤ 5 × 10⁴, and s consists of English letters, digits, symbols and spaces. That last line matters: the alphabet is printable ASCII, so a fixed-size array works as the lookup table. It also tells you an O(n²) solution with 2.5 × 10⁹ steps in the worst case is not going to pass comfortably.

Two words in the statement deserve attention before writing code. Substring means contiguous. Length means you return a number, not the string (returning the string is a common follow-up, covered below).

Brute Force: Check Every Substring

The most direct approach: for every start index i, extend the end index j one character at a time and stop as soon as you see a repeat. Keep a set of characters seen since i.

def length_of_longest_substring_brute(s: str) -> int:
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break              # every longer substring from i also repeats
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best

A fully naive version generates all O(n²) substrings and checks each in O(n), for O(n³). The early break brings it to O(n · min(n, m)) where m is the alphabet size, because a window without repeats can never be longer than m characters. With m = 95 printable characters this actually passes on LeetCode, which surprises people. In an interview it's still the warm-up, not the answer: the interviewer wants to see you notice the wasted work.

Where the brute force wastes time

Take "abcabcbb". Starting at i = 0, we scan "abc" and stop at the second 'a'. Then we start over at i = 1 and rescan "bc" before reaching the same 'a'. We already knew "bc" was duplicate-free. Every restart throws away information about the characters between the old start and the duplicate.

The fix is to keep the window and only adjust its left edge. That observation is the whole sliding window idea: when s[i..j] has no repeats, so does every substring inside it, so we never need to re-verify them.

Sliding Window with a Set: O(n)

Maintain a window [left, right] that always contains distinct characters, plus a set holding exactly those characters.

1. Expand. Move right forward one character at a time.
2. Repair. If s[right] is already in the set, the window is invalid. Remove s[left] from the set and advance left, repeating until s[right] is no longer in the set.
3. Record. Add s[right] to the set. The window is valid again; update the best length with right − left + 1.

def length_of_longest_substring_set(s: str) -> int:
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:          # shrink until ch is unique again
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

Why the nested loop is still O(n)

Interviewers almost always ask this, because the code has a while inside a for. The answer is an amortised argument: left only ever moves forward, and it can move at most n times in total across the whole run. Each character is added to the set once (when right passes it) and removed at most once (when left passes it). So the total work is at most 2n set operations, which is O(n).

Why it is correct

Two facts make the window safe:

• Validity is monotonic. If a window contains a duplicate, every larger window containing it also does. So when s[right] creates a duplicate, no window starting at the current left (or any position before the earlier copy of s[right]) can be extended past right. Moving left past that earlier copy loses nothing.
• Every candidate end is checked. For each right, the loop finds the smallest left that makes s[left..right] duplicate-free, which is the longest valid substring ending at right. The answer is the maximum over all ends.

Optimised Sliding Window: Jump with an Index Map

The set version removes characters one at a time until the duplicate leaves the window. But we can compute exactly where left needs to go: one position past the previous occurrence of s[right]. If we store the last index of every character, the left pointer can jump there in O(1).

def length_of_longest_substring(s: str) -> int:
    last = {}                      # char -> last index where it appeared
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1    # jump past the previous copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best

The condition last[ch] >= left is the important part. The map is never cleaned up, so it remembers characters that are already outside the window. If the previous copy of ch sits to the left of the current window, it isn't a duplicate inside the window at all, and jumping to it would move left backwards. You can write the same guard as left = max(left, last[ch] + 1); both versions keep left monotonic.

Set vs index map: does the optimisation matter?

Both are O(n). The index map does at most n steps instead of 2n and avoids set removals, so it's slightly faster in practice. The set version is easier to get right and generalises more naturally to "at most K distinct", where you genuinely need counts and can't jump. In an interview I'd present the set version first if you're nervous, then say "we can skip the inner loop by remembering last positions" and write the index-map version. Showing both is stronger than showing only the clever one.

Dry Runs: "abcabcbb" and "abba"

Dry run 1: s = "abcabcbb" (index map)

Answer: 3. Notice the jump at right = 6: the previous 'b' was at index 4, so left leaps from 3 to 5 in one step. The set version would have removed 'a' and 'b' individually to get there.

Dry run 2: s = "abba" (why the guard exists)

At right = 3, the stored position of 'a' is 0, which is already outside the window [2, 3]. The guard ignores it. Without the guard, left would become 1, the window would be "bba", and the answer would wrongly be 3.

Dry run 3: s = "dvdf" (why you can't just restart)

A tempting wrong idea is "when you hit a duplicate, start a fresh window at the duplicate". On "dvdf": window "dv", then 'd' repeats, restart at index 2 with "d", then "df", answer 2. But the true answer is 3 ("vdf"). The correct move is to put left just past the earlier 'd' (index 1), keeping 'v' in the window. The index-map formula does exactly that: left = last['d'] + 1 = 1.

LeetCode 3 Solution Code in Python, C++ and Java

All three use a fixed array of size 128 or 256 instead of a hash map, since the input is ASCII. The array is initialised to −1, meaning "not seen", which makes the guard a single comparison.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = [-1] * 128
        left = best = 0
        for right, ch in enumerate(s):
            c = ord(ch)
            if last[c] >= left:
                left = last[c] + 1
            last[c] = right
            if right - left + 1 > best:
                best = right - left + 1
        return best

If the input could contain characters beyond ASCII, swap the list for a dict as in the earlier version. ord(ch) on a non-ASCII character would index past 127 and raise an error.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last(256, -1);          // last index of each byte value
        int left = 0, best = 0;
        for (int right = 0; right < (int)s.size(); ++right) {
            unsigned char c = s[right];       // avoid negative index for chars > 127
            if (last[c] >= left) left = last[c] + 1;
            last[c] = right;
            best = max(best, right - left + 1);
        }
        return best;
    }
};

The unsigned char cast is a small detail that interviewers who write C++ notice. On most platforms char is signed, so a byte above 127 would become a negative index and cause undefined behaviour.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        java.util.Arrays.fill(last, -1);
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (last[c] >= left) left = last[c] + 1;
            last[c] = right;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Java's char is an unsigned 16-bit value, so for full Unicode input you would use an int[65536] or a HashMap<Character, Integer>. For this problem's constraints, 128 is enough.

The set-based version in C++

Some interviewers prefer the explicit shrink loop because it maps directly onto the general template. Here it is with a boolean array:

int lengthOfLongestSubstringSet(const string& s) {
    bool inWindow[256] = {false};
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        unsigned char c = s[right];
        while (inWindow[c]) {                 // shrink until c leaves the window
            inWindow[(unsigned char)s[left]] = false;
            ++left;
        }
        inWindow[c] = true;
        best = max(best, right - left + 1);
    }
    return best;
}

Complexity Analysis

On space: with a fixed 128-entry array, space is O(1) in the sense that it doesn't grow with n. With a hash map it's O(min(n, m)) because the map holds at most one entry per distinct character. Say both and you've covered the follow-up "what if the input is Unicode?". For a refresher on how to argue amortised bounds like the 2n one, see time and space complexity explained.

Variants and Follow-Up Questions

Because LeetCode 3 is so well known, many interviewers treat it as a warm-up and spend the remaining time on a twist. The good news is that most twists reuse the same expand-and-shrink loop with a different validity check.

1. Return the substring, not the length

Record where the best window starts whenever you improve it.

def longest_unique_substring(s: str) -> str:
    last = {}
    left = best_len = best_start = 0
    for right, ch in enumerate(s):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = right
        if right - left + 1 > best_len:
            best_len, best_start = right - left + 1, left
    return s[best_start:best_start + best_len]

With strict > you return the first longest substring; with >=, the last. Ask which one the interviewer wants if it matters.

2. Longest substring with at most K distinct characters (LeetCode 340, and 159 for K = 2)

Now repeats are allowed, but the window may hold at most K different characters. You can't jump any more, because removing one character from the left doesn't tell you whether a distinct character has fully left the window. Keep a frequency map instead and shrink while the number of keys exceeds K.

from collections import defaultdict

def longest_k_distinct(s: str, k: int) -> int:
    count = defaultdict(int)
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        while len(count) > k:
            out = s[left]
            count[out] -= 1
            if count[out] == 0:
                del count[out]       # a distinct character left the window
            left += 1
        best = max(best, right - left + 1)
    return best

LeetCode 904 (Fruit Into Baskets) is this exact problem with K = 2 dressed up as a story. LeetCode 3 itself is a special case of a related idea: a window is duplicate-free exactly when its number of distinct characters equals its length.

3. Each character at most twice (LeetCode 3090) or at most K times

Change the rule from "no repeats" to "no character more than K times". The validity check becomes "the count of the character just added is at most K". Since only the newly added character can break the rule, shrink while count[ch] > k:

def longest_each_at_most_k(s: str, k: int) -> int:
    count = {}
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > k:
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

With k = 1 this is LeetCode 3 again. Writing it this way in an interview shows you see the general shape, not just one memorised solution.

4. Count all substrings with no repeating characters

For each right, the window [left, right] is the longest valid substring ending at right. Every substring that ends at right and starts anywhere in [left, right] is also valid (a piece of a duplicate-free string is duplicate-free). That's right − left + 1 substrings. Sum it up:

def count_unique_substrings(s: str) -> int:
    last = {}
    left = total = 0
    for right, ch in enumerate(s):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = right
        total += right - left + 1
    return total

# "abc" -> 6 (a, b, c, ab, bc, abc); "aa" -> 2 (a, a)

This counting trick (add the window length at each step) appears in many "count subarrays where..." problems and is worth memorising on its own.

5. Longest repeating character replacement (LeetCode 424)

You may change up to K characters; find the longest substring of one repeated letter after changes. The window is valid when window length − (count of its most frequent letter) ≤ K. Same skeleton, different check. It's a favourite follow-up because the "max frequency doesn't need to decrease when shrinking" trick is subtle; the sliding window guide walks through why.

6. The input is a stream, or the string is huge

The index-map solution reads each character once and never looks back except through the map, so it already works on a stream if you only need the length. Memory stays O(alphabet). If you need to output the substring itself, you must buffer the current window, which can be up to alphabet-size characters long. That's a nice point to raise unprompted.

Related problems worth solving next

The shortest-window variant flips the template (shrink while valid instead of while invalid); LeetCode 76 Minimum Window Substring is the canonical example.

How to Present LeetCode 3 in an Interview

Since most interviewers expect you to have seen this problem, your score depends less on reaching O(n) and more on how clearly and carefully you get there. A strong 15-minute run looks like this:

1. Clarify the input (1 minute). "Is it ASCII or can it be Unicode? Can it be empty? Do you want the length or the substring? Is it case-sensitive, so 'a' and 'A' are different?" These questions take seconds and justify your choice of array vs hash map.
2. State the brute force in one sentence (1 minute). "For every start, extend until a repeat: O(n²). The waste is that each restart re-scans characters we already know are unique." Don't code it unless asked.
3. Explain the window invariant (2 minutes). "I'll keep s[left..right] duplicate-free. When the new character is already inside, I move left past its previous occurrence." Saying the invariant out loud is the single most convincing thing you can do.
4. Code the index-map version (5 minutes). Use clear names: left, right, last, best. Avoid i, j, mp.
5. Dry run "abba" yourself (2 minutes). Don't wait for the interviewer to find the bug. Walking through the case that breaks most solutions shows you know where the risk is.
6. State complexity with the argument (1 minute). O(n) time because each index is visited once; O(1) space for a fixed alphabet, O(min(n, m)) with a map.

Follow-ups to expect

• "Why is your while loop not O(n²)?" Amortised: left moves at most n times in total.
• "What if the string has emojis?" Use a hash map keyed by code point. In Java, iterate with codePoints() because one emoji can be two char values (a surrogate pair).
• "Now allow at most K distinct characters." Switch to a frequency map; you can no longer jump.
• "How many such substrings exist?" Sum of window lengths.
• "Can you do it without extra space?" Not in O(n) for a general alphabet; with a fixed alphabet the array is already constant space. An honest "no, and here's why" beats a forced answer.

Common Mistakes on LeetCode 3

• Missing the guard in the index-map version. left = last[ch] + 1 without max fails on "abba". This is the most common bug in submissions and in interviews.
• Restarting the window at the duplicate. Fails "dvdf". The new left is one past the earlier copy, not the current position.
• Updating best before fixing the window. In the set version, compute right − left + 1 only after the shrink loop and after adding the new character.
• Forgetting to update last[ch] on every step. It must store the most recent index, even when no jump happened.
• Off-by-one in the length. The window [left, right] is inclusive, so its length is right − left + 1.
• Signed char indexing in C++. Use unsigned char or a size-256 array with a cast.
• Confusing substring and subsequence. If you find yourself thinking "pwke", reread the problem.
• Empty string. All the solutions above return 0 for "" naturally, but a version that initialises best = 1 doesn't.

A quick self-test before you submit

Run these five inputs mentally: "" → 0, " " → 1, "bbbbb" → 1, "abba" → 2, "dvdf" → 3. If your code passes all five, it handles the empty case, the single-character case, the all-duplicates case, the stale-index case and the "keep the middle" case. That covers nearly every wrong answer I see on this problem.

Once LeetCode 3 feels automatic, pair it with hash map interview problems and the two pointers technique. The index-map trick here is really a hash map storing "last seen position", the same idea behind Two Sum and many prefix-sum problems, and the two moving pointers are a special case of the two-pointer family. Seeing those connections is what lets you solve the next unseen string problem instead of just this one.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.