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).

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

• Invariant: all characters in s[l:r+1] are unique.
• The window state exactly matches the elements in s[l..r].
• Shrinking/expanding preserves validity, so any recorded window is correct.
• The best recorded window is optimal because all candidate windows are considered.

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.

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.