Back to Two Pointers and Sliding Window
Longest Substring Without Repeating Characters
Expand the right pointer adding characters; shrink the left pointer when a duplicate enters. The window always contains a unique-character substring.
Visualization
Speed
–
Current Window
0
Current Length
0
Max Length
0
a
–1
b
–2
c
–3
a
–4
b
–5
c
–6
b
–7
b
–Left pointer (L)Right pointer (R)In windowDuplicate foundMax window (final)
Ready — press Play or step through.
Complexity
O(n)
Time
O(k)
Space
O(n)
Best Case
O(n)
Worst Case
Space is O(k) where k is the size of the character set (e.g., 26 for lowercase ASCII, 128 for full ASCII). In practice this is a small constant.
How It Works
- 1Initialize left=0, empty char_map, maxLen=0
- 2Expand right pointer one step. If s[right] was seen and its index is >= left, move left past it
- 3Update char_map[s[right]] = right
- 4Update maxLen = max(maxLen, right - left + 1) and repeat
Applications
- •Token stream parsing: longest run of distinct tokens
- •Password strength: finding unique-character runs
- •DNA/protein analysis: longest unique amino-acid sequence windows
- •File deduplication: identifying non-repeating byte sequences
Active Recall Quiz
Question 1 of 3
Why do we check `char_map[s[right]] >= left` instead of just checking `s[right] in char_map`?