Handbooks / Data Structures & Algorithms / Chapter 3
String Algorithms
7 pages · ~5 min✓ Reviewed
Builds on Arrays and Hashing. Next up: Linked Lists, Stacks and Queues.
Sliding Window and Frequency Counts
1. The Window
- Keep a range [l, r] and update state incrementally
- O(n) instead of O(n^2) re-scanning
| Fixed size k | Variable | |
|---|---|---|
| Grow | add s[r] | expand r |
| Shrink | drop s[r-k] once longer than k | move l while invalid |
2. Longest Without Repeats
- Map
last[c]holds the last index of each char - Jump l = max(l, last[c]+1)
- O(n) time, O(alphabet) space
python
last = {}; l = best = 0
for r, c in enumerate(s):
l = max(l, last.get(c, -1) + 1)
last[c] = r
best = max(best, r - l + 1)3. Anagram Windows
- Compare a 26-slot count array (or map) of window vs pattern
- Track a matched counter; a slide touches only two slots
- Each slide is O(1), not an array re-compare