String And Sliding Window Algorithms

What's being tested

These problems test string scanning, substring enumeration, and sliding-window invariants under character-count, dictionary, or movement constraints. Interviewers look for whether you can reduce brute-force substring checks to linear or near-linear algorithms using counts, hashes, tries, or two pointers.

Patterns & templates

• Sliding window with frequency counts — maintain need, have, and formed; expand right, contract left; typical O(n) time, O(Σ) space.

• Anagram detection via multisets — compare character counts instead of sorting each substring; O(n * alphabet) or optimized O(n) rolling deltas.

• Substring membership checks — use HashSet<String> for direct lookup; for many prefixes, use a Trie or dynamic programming like word-break.

• Binary search on answer length — for longest duplicate substring, check existence with rolling hash or suffix-array-style logic; target O(n log n).

• Movement/token invariants — scan both strings while skipping blanks; verify token order, wall positions, and directional constraints in O(n) time.

• Multiplicity-aware coverage — minimum covering substring requires exact counts, not just presence; decrement carefully when shrinking the window.

Common pitfalls

Pitfall: Sorting every candidate substring for anagram checks often turns an intended O(n) or O(nk) solution into O(nk log k).

Pitfall: Treating dictionary-word checks as greedy prefix matching fails; use DP or backtracking with memoization when segmentation is ambiguous.

Pitfall: Rolling hash solutions need collision discussion; mention double hashing or final substring verification.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.