Longest Substring Without Repeating Characters

A repeated character is not a reason to restart the scan. It is a reason to move the left boundary to the first position that makes the current window valid again.

Start With the Contract

Given a string s, return the length of its longest substring in which every character appears at most once.

The output is a number. You do not need to return the substring itself.

A substring is contiguous. In "pwwkew", "wke" is a substring because its characters occupy adjacent positions. "pwke" is a subsequence, not a substring, because it skips the second "w".

The input may be empty, may contain up to 10^5 characters, and may include letters, digits, symbols, and spaces. That rules out assumptions such as “the input contains only lowercase English letters.”

The solution direction is:

1. Scan the string from left to right.
2. Maintain a window whose characters are all distinct.
3. Remember the most recent index of each character.
4. When a repeat appears, jump the left boundary past the earlier occurrence.
5. Track the largest valid window seen so far.

That is the core of the longest substring Python solution. The useful part is not memorizing the code. It is knowing what the window guarantees after every iteration.

Recognize the Sliding-Window Signal

This problem has three structural cues:

• The candidate must be contiguous.
• The candidate has a clear validity condition: no character repeats.
• The objective is to maximize its length.

Those cues suggest a variable-size sliding window. Represent the current candidate as:

[ [left, right] ]

The right boundary moves forward through the string. The left boundary moves forward only when the window becomes invalid.

The window behaves like a movable frame:

• Expand it by advancing right.
• If the new character is safe, keep expanding.
• If it creates a duplicate, discard the conflicting prefix.
• Measure the repaired window.

This is different from a subsequence problem, where skipped characters are allowed. It is also different from a prefix-sum problem. Prefix sums are useful when cumulative values answer range queries; here, the important state is a changing boundary and the characters currently allowed inside it.

The key decision is whether to restart or repair. Restarting throws away information. The prefix before the duplicate has already been checked. Keep the work. Move only the boundary that must change.

Build a Brute-Force Baseline

Before optimizing, establish a simple correct method.

For every starting index:

1. Create an empty set of seen characters.
2. Extend the candidate one character at a time.
3. If the next character is already in the set, stop for this starting index.
4. Otherwise, add it and update the best length.

Stopping is safe. Once a candidate starting at i contains a duplicate, every longer candidate with the same start also contains that duplicate.

def longest_substring_brute_force(s: str) -> int:
    best = 0

    for start in range(len(s)):
        seen = set()

        for end in range(start, len(s)):
            if s[end] in seen:
                break

            seen.add(s[end])
            best = max(best, end - start + 1)

    return best

This takes O(n²) time in the worst case. The outer loop chooses a start, and the inner loop may scan most of the remaining string. The set uses O(u) space, where u is the number of distinct characters encountered.

The baseline is useful as a debugging reference, but it repeats work. Neighboring start positions repeatedly validate characters that a previous candidate already proved unique. With input length up to 10^5, that repeated scanning is the bottleneck.

The optimized version keeps one moving window instead of rebuilding many overlapping candidates.

Derive the Valid Window

The most important statement is the invariant:

After the current character has been processed, every character in s[left:right + 1] appears at most once.

Each variable has a specific obligation:

State	Obligation
right	Scans every input character exactly once
left	Marks the earliest boundary of the current valid window
last_seen[c]	Stores the most recent processed index of character c
best	Stores the largest valid window length found so far

Suppose the current character is s[right], and its previous occurrence was at previous_index.

There are two cases:

1. previous_index < left: the old occurrence is outside the current window. It does not conflict with the window, so left stays where it is.
2. previous_index >= left: the old occurrence is inside the current window. To remove the duplicate, move left to previous_index + 1.

The update must be guarded:

left = max(left, previous_index + 1)

Why? Because last_seen contains history for the entire processed prefix, not only characters inside the current window. An old occurrence can be stale relative to left. Using it directly could move left backward and reintroduce characters that the current window had already excluded.

Only after repairing the window should you calculate:

right - left + 1

That length formula includes both endpoints.

Prove the Jump

Assume the current window before adding s[right] is valid.

If s[right] has a previous occurrence at previous_index inside the window, then any valid window ending at right must begin after previous_index. A start at or before previous_index would include both copies of the character.

So every boundary from left through previous_index is unsafe for this right endpoint. The earliest safe boundary is exactly:

previous_index + 1

Jumping there removes the conflict in one operation.

This gives a compact induction argument:

1. The previous window is valid.
2. Adding s[right] can introduce at most one new duplicate: the character at right.
3. If its old occurrence is in the window, moving left past that occurrence removes the conflict.
4. The repaired window is valid again.
5. Update the best length from that valid window.

The pointers only move forward. right advances once per character. left never moves backward, even when it jumps several positions. Therefore, the total pointer movement is linear.

The dictionary is historical state, not a live inventory of the current window. That distinction explains both the max guard and why stale indices are safe.

Trace Repeats and Stale Indices

Use "pwwkew" as a dry run. Indices are zero-based.

right	Character	Previous index	left after repair	Current window	best
0	p	—	0	p	1
1	w	—	0	pw	2
2	w	1	2	w	2
3	k	—	2	wk	2
4	e	—	2	wke	3
5	w	2	3	kew	3

At right = 2, the second w conflicts with the w at index 1. The left boundary jumps from 0 to 2.

At right = 5, the previous w is at index 2, which is still inside the current window [2, 4]. The boundary moves to 3.

Now consider a stale index. Suppose left is already 3 and the current character's stored index is 1. That occurrence is before the window. Moving left to 2 would be a bug: the boundary would travel backward. The guard prevents it.

This incorrect version looks plausible:

left = previous_index + 1

It fails because the map remembers old positions. The correct version preserves monotonic movement:

left = max(left, previous_index + 1)

Several windows can have the same maximum length. The algorithm does not need to choose a particular witness substring; it only returns the required length.

Implement the Python Solution

The last-seen dictionary makes the decisive state transition explicit:

def length_of_longest_substring(s: str) -> int:
    last_seen = {}
    left = 0
    best = 0

    for right, char in enumerate(s):
        if char in last_seen:
            left = max(left, last_seen[char] + 1)

        last_seen[char] = right
        best = max(best, right - left + 1)

    return best

Read the code as a sequence of obligations:

• enumerate supplies the scanning index right.
• last_seen answers where the current character was most recently found.
• left jumps past a conflicting occurrence but never moves backward.
• Updating last_seen[char] records the newest occurrence for future repeats.
• best is updated only after the window is valid.

Empty input needs no special branch. The loop runs zero times, so best remains 0.

The dictionary is intentionally character-agnostic. A space is a key. A punctuation mark is a key. A digit is a key. There is no lowercase-only array and no trimming step that could silently change the problem.

An equivalent implementation uses a frequency map and repeatedly moves left until the duplicate count returns to one. That version is often useful when the validity condition is more complicated. For this problem, I prefer the last-seen jump because it exposes the exact repair operation: the boundary moves directly to the earliest safe position.

Complexity and Edge-Case Checks

Let n be the string length and u the number of distinct characters encountered.

• Time: O(n). The right boundary scans the string once. The left boundary only moves forward.
• Auxiliary space: O(u). The dictionary stores one latest index per distinct character.

Test cases should target assumptions, not just happy paths:

Input	Expected result	What it checks
""	0	Empty input
"a"	1	Single character
"aaaa"	1	Repeated character repair
"abcdef"	6	Entire string is valid
"abcabcbb"	3	Repeated windows and ties
"pwwkew"	3	Jumping across a duplicate
"a b!a"	4	Spaces and symbols
"abba"	2	Stale-index guard

For "a b!a", the longest valid substring is "a b!", with length 4. The space and exclamation mark are ordinary characters; they must not be removed or normalized.

For "abba", the final a has an earlier index of 0, but the current window begins at 2. The old a is stale. Without max, left would move backward from 2 to 1, breaking the invariant.

Two off-by-one points cause many otherwise correct submissions to fail:

• Jump past the old occurrence: previous_index + 1.
• Measure an inclusive window: right - left + 1.

The Transferable Pattern

The reusable interview rule is broader than this one string problem:

When you need the best contiguous interval under a validity condition, maintain the invariant first. Then ask what state detects a violation and whether the boundary can jump directly to the earliest safe position.

For this problem:

• Contiguity gives us a window.
• The no-duplicates rule gives us the invariant.
• last_seen detects the violation.
• The previous index gives us the jump target.
• Monotonic boundaries give us linear total movement.

Before submitting, verify three things:

1. best is updated only after the window is valid.
2. left never moves backward.
3. The implementation treats empty input, spaces, symbols, and digits as real input rather than hidden exceptions.

A good sliding-window solution is not a pointer template. It is a maintained promise: this window is valid, and I know exactly why.