044. Longest Substring Without Repeats

Why this mechanism works

When the incoming character repeats inside the active window, its previous occurrence must be excluded. Store last-seen indices and jump the left boundary directly past that occurrence. Never move left backward when the previous occurrence lies outside the active window.

State and boundaries

[left,right+1) is duplicate-free after repair. last records the most recent index of each character anywhere in the processed prefix.

Protocol

1. Read the incoming character's last position.
2. Raise left to at least one past that position.
3. Record its new position.
4. Commit the repaired window length to best.

Visualization

a b b a
0 1 2 3
second b moves left to 2
last a=0 must not move left backward

Python implementation

def longest_unique_substring(text):
    last = {}
    left = best = 0
    for right, char in enumerate(text):
        if char in last:
            left = max(left, last[char] + 1)
        last[char] = right
        best = max(best, right - left + 1)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 longest_unique_substring: last = {}
text='abcabcbb'; last={}

L3 longest_unique_substring: left = best = 0
text='abcabcbb'; last={}; left=0; best=0

L4 longest_unique_substring: for right, char in enumerate(text):
text='abcabcbb'; last={}; left=0; best=0; right=0; char='a'

L7 longest_unique_substring: last[char] = right
text='abcabcbb'; last={'a':0}; left=0; best=0; right=0; char='a'

L8 longest_unique_substring: best = max(best, right - left + 1)
text='abcabcbb'; last={'a':0}; left=0; best=1; right=0; char='a'

L4 longest_unique_substring: for right, char in enumerate(text):
text='abcabcbb'; last={'a':0}; left=0; best=1; right=1; char='b'

L7 longest_unique_substring: last[char] = right
text='abcabcbb'; last={'a':0, 'b':1}; left=0; best=1; right=1; char='b'

L8 longest_unique_substring: best = max(best, right - left + 1)
text='abcabcbb'; last={'a':0, 'b':1}; left=0; best=2; right=1; char='b'

... 14 intermediate state changes omitted ...

L7 longest_unique_substring: last[char] = right
text='abcabcbb'; last={'a':3, 'b':6, 'c':5}; left=5; best=3; right=6; char='b'

L4 longest_unique_substring: for right, char in enumerate(text):
text='abcabcbb'; last={'a':3, 'b':6, 'c':5}; left=5; best=3; right=7; char='b'

L6 longest_unique_substring: left = max(left, last[char] + 1)
text='abcabcbb'; last={'a':3, 'b':6, 'c':5}; left=7; best=3; right=7; char='b'

L7 longest_unique_substring: last[char] = right
text='abcabcbb'; last={'a':3, 'b':7, 'c':5}; left=7; best=3; right=7; char='b'

L2 longest_unique_substring: last = {}
text='abba'; last={}

L3 longest_unique_substring: left = best = 0
text='abba'; last={}; left=0; best=0

L4 longest_unique_substring: for right, char in enumerate(text):
text='abba'; last={}; left=0; best=0; right=0; char='a'

L7 longest_unique_substring: last[char] = right
text='abba'; last={'a':0}; left=0; best=0; right=0; char='a'

L8 longest_unique_substring: best = max(best, right - left + 1)
text='abba'; last={'a':0}; left=0; best=1; right=0; char='a'

L4 longest_unique_substring: for right, char in enumerate(text):
text='abba'; last={'a':0}; left=0; best=1; right=1; char='b'

L7 longest_unique_substring: last[char] = right
text='abba'; last={'a':0, 'b':1}; left=0; best=1; right=1; char='b'

L8 longest_unique_substring: best = max(best, right - left + 1)
text='abba'; last={'a':0, 'b':1}; left=0; best=2; right=1; char='b'

... 1 intermediate state changes omitted ...

L6 longest_unique_substring: left = max(left, last[char] + 1)
text='abba'; last={'a':0, 'b':1}; left=2; best=2; right=2; char='b'

L7 longest_unique_substring: last[char] = right
text='abba'; last={'a':0, 'b':2}; left=2; best=2; right=2; char='b'

L4 longest_unique_substring: for right, char in enumerate(text):
text='abba'; last={'a':0, 'b':2}; left=2; best=2; right=3; char='a'

L7 longest_unique_substring: last[char] = right
text='abba'; last={'a':3, 'b':2}; left=2; best=2; right=3; char='a'

Why the solution is correct

Before insertion the window is unique, so the incoming character is the only possible new duplicate. Removing its earlier occurrence and everything before it restores uniqueness with the longest possible suffix. Maximizing these longest valid suffixes covers the optimal substring.

Time and space

O(n) expected time and O(u) auxiliary space.

Common mistakes

Assigning left=last[char]+1 without max can move backward in abba. Updating last before querying loses the previous index.

Reasoning card

Transfer exercise

Return the earliest longest substring itself while retaining a strict best-length improvement rule.