LeetCode Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters is LeetCode problem 3, rated Medium. It is the prototypical sliding window problem and one of the highest-yield patterns for string interview questions. If you internalize this one, half the medium-tier string problems become muscle memory.

The Problem

Given a string s, find the length of the longest substring that contains no repeated characters.

Example:

Input:  s = "abcabcbb"
Output: 3
Explanation: "abc" has length 3.

“Substring” means contiguous. “Subsequence” would be a different and much harder problem.

Brute Force

Try every substring; check whether it has unique characters.

def length_of_longest_substring(s):
    best = 0
    n = len(s)
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best

Time: O(n^2) in practice because the inner loop breaks early on a repeat. The naive triple-nested version is O(n^3). Space: O(min(n, alphabet)). For n = 5 * 10^4 the quadratic version is borderline.

Optimal Solution

Use a sliding window with a hash map from character to its most recent index. As we advance the right edge, if the character has been seen inside the current window, jump the left edge just past the previous occurrence.

def length_of_longest_substring(s):
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Line by line:

• last[ch] stores the most recent index where ch appeared.
• left is the start of the current valid window.
• For each right, if we have seen ch before and that prior occurrence is inside the current window, jump left to one past it.
• Update last[ch] to the new index.
• Update best with the current window width.

The condition last[ch] >= left is the subtle bit. A character could have been seen long ago but already excluded from the current window, in which case it does not constrain us.

Walk Through an Example

s = "abcabcbb".

• right = 0, ch = ‘a’. last = {a: 0}. window “a”, best = 1.
• right = 1, ch = ‘b’. last = {a: 0, b: 1}. window “ab”, best = 2.
• right = 2, ch = ‘c’. last = {a: 0, b: 1, c: 2}. window “abc”, best = 3.
• right = 3, ch = ‘a’. Seen at 0, which is >= left (0). left = 1. last[a] = 3. window “bca”, best = 3.
• right = 4, ch = ‘b’. Seen at 1, which is >= left (1). left = 2. last[b] = 4. window “cab”, best = 3.
• right = 5, ch = ‘c’. Seen at 2, which is >= left (2). left = 3. last[c] = 5. window “abc”, best = 3.
• right = 6, ch = ‘b’. Seen at 4, which is >= left (3). left = 5. last[b] = 6. window “cb”, best = 3.
• right = 7, ch = ‘b’. Seen at 6, which is >= left (5). left = 7. last[b] = 7. window “b”, best = 3.

Return 3.

Edge Cases

• Empty string. Return 0. The loop never executes.
• All identical characters like "aaaa". The window stays width 1.
• All unique characters. The window grows to the full string.
• Strings with spaces, digits, punctuation. The algorithm is character-agnostic.
• Unicode. Python handles unicode strings transparently; the hash map keys are code points.

Complexity Analysis

• Time: O(n). Each character is visited once by the right pointer. left only advances, never retreats, so the work is linear.
• Space: O(min(n, alphabet)) for the hash map. For ASCII this is O(1) bounded by 128 or 256.

How to Explain It in an Interview

• Restate the problem and confirm substring versus subsequence.
• Quote the O(n^2) brute force in one sentence and move on.
• Sketch the sliding window: a window that always contains unique characters, expanded on the right and contracted on the left only when needed.
• Justify the use of a hash map of last-seen indices so that contraction is O(1) instead of a linear scan.
• Walk through the last[ch] >= left guard. This is the bug source for most candidates.
• State O(n) time and bounded space.

Related Problems

• LeetCode 159 Longest Substring with At Most Two Distinct Characters
• LeetCode 340 Longest Substring with At Most K Distinct Characters
• LeetCode 76 Minimum Window Substring
• LeetCode 567 Permutation in String
• LeetCode 424 Longest Repeating Character Replacement

The whole pattern family is in sliding window technique, and the hash map mechanics come from hashing and hash maps.

Wrap up

This problem rewards a clean sliding window template more than any clever trick. Write the skeleton, “expand right, contract left on violation, update answer”, and almost every variable-size window problem falls out of it. Get it cold and you will see the same shape in dozens of follow-ups.