Arrays, Strings, and Hashing

What's being tested

These problems test string scanning, array filtering, and hash-based frequency reasoning under tight correctness constraints. Interviewers are looking for clean handling of substrings, prefixes, character/digit multisets, and movement invariants with predictable O(n) or O(n * k) complexity.

Patterns & templates

• Frequency maps for anagrams — compare `Counter`/fixed-size arrays; use O(1) alphabet-sized comparisons when characters are bounded.

• Substring enumeration — nested loops generate s[i:j]; expect O(n^2) substrings, so pair with set lookup or pruning.

• Prefix filtering — use word.startswith(prefix) for simple scans in O(total_chars); use a Trie only when many repeated prefix queries exist.

• Sliding window for fixed-length chunks — maintain character counts incrementally instead of rebuilding each substring in O(k) time.

• Invariant checking for token transforms — ignore empty spaces, preserve token order, and validate directional movement constraints in one pass.

• Digit feature extraction — convert each number to unique digits, update frequency buckets 0..9, and return the largest bucket count.

Common pitfalls

Pitfall: Treating anagrams as sorted strings everywhere can add avoidable O(k log k) cost per substring.

Pitfall: Forgetting duplicate handling; clarify whether duplicate dictionary words should be returned once or preserved.

Pitfall: For transform problems, matching token counts is not enough; direction and wall constraints must also remain valid.