Longest Substring Without Repeating Characters

Given a string s, return the length of the longest substring without repeating characters.

A sliding window plus a last-seen index map solves this in O(n).

Why this is worth learning

A last-seen position is useful only when it lies inside the current window. The left boundary must never move backward.

Before coding: one-minute experiment

On "abba", why must the final a not move left back from 2 to 1?

Function signature

func LengthOfLongestSubstring(s string) int

Inputs / outputs

• s: input string (ASCII).
• Return: length of the longest substring with all unique characters.

Example

s = "abcabcbb"
Output: 3

Longest substring is "abc".

Constraints

• 0 <= len(s) <= 100_000

Core idea (near-solution)

Maintain a window [l, r] with all unique characters. Track the last index where each character was seen. If you see a repeated character, move l past its previous index.

Invariant: all characters in s[l:r+1] are unique.

Algorithm (step-by-step)

1. Initialize l = 0, best = 0, and a map last from byte to index.
2. For each r from 0 to len(s)-1:
   • If s[r] was seen at index idx and idx >= l, set l = idx + 1.
   • Update last[s[r]] = r.
   • Update best = max(best, r-l+1).
3. Return best.

Correctness sketch

Before adding s[r], the active substring contains no duplicate byte. If the previous occurrence of s[r] is inside it, any valid substring ending at r must begin after that occurrence; advancing left to last+1 removes precisely the conflict. If the occurrence is before left, it imposes no new restriction. Thus left=max(left,last+1) gives the earliest valid start for this endpoint, hence its longest unique substring. Store the new occurrence and compare its length with best. Processing every right endpoint considers the longest feasible substring ending at each one, which is sufficient for the global maximum.

Trace (hand walkthrough)

Example input:
s = "abcabcbb"
Output: 3

Longest substring is "abc".

Walk:
- r=0..2 builds "abc", best=3
- r=3 sees a (last at 0) -> l moves to 1, window "bca"
- r=4 sees b (last at 1) -> l=2, window "cab"
- r=5 sees c (last at 2) -> l=3, window "abc" (best stays 3)

Pitfalls to avoid

• Moving l backward (must use max(l, last+1)).
• Forgetting to update last after moving l.

Debugging lens

Use "abba", repeated single bytes, and an empty string. Distinguish last index from last index plus one in the representation. The answer counts bytes under the stated ASCII domain.

Complexity

• Time: O(n)
• Extra space: O(k) where k is the alphabet size.

Implementation notes (Go)

• Store last seen indices in a map and update left = max(left, last+1).
• Update the answer as right-left+1.

Reconstruction checkpoint

On "abba", why must the final a not move left back from 2 to 1?

Return to Sliding Window · Module quiz