Arrays, Strings And Hash Counting

What's being tested

These problems test frequency counting, hash-based lookup, prefix invariants, and careful distinctions between subsequences, substrings, partitions, and anagrams. You should demonstrate how to reduce brute force with counters, sets, or structured scans while stating time and space complexity and handling empty inputs, repeated characters, and boundary positions.

Patterns & templates

• Frequency signature for anagrams — count characters with a fixed array or map; grouping is O(nm) for n strings of length m, plus output storage.

• Hash map lookup — store counts, last positions, or canonical keys for expected O(1) average access; distinguish worst-case guarantees from practical performance.

• Prefix invariant — after each update, verify whether every position in a required prefix is active; track the current prefix boundary instead of rescanning all positions.

• Greedy partitioning — maintain a character set for the current repeat-free piece; when a duplicate appears, close the piece and reset in O(n) time.

• Two-pointer subsequence scan — advance through the candidate substring while matching characters from the source; subsequence matching is non-contiguous, substring matching is contiguous.

• Deletion and substitution evaluation — enumerate each candidate removed character or local replacement, then scan efficiently; avoid mutating the original string repeatedly.

• Complexity discipline — state whether O(nm), O(n + alphabet), or O(n²) is acceptable, and include hash-map space plus result/output space.

Common pitfalls

Pitfall: Treating anagrams as sorted strings everywhere can add O(m log m) per string; frequency vectors are typically faster and deterministic for bounded alphabets.

Pitfall: Confusing a subsequence with a substring leads to invalid matches; explicitly track whether selected characters must remain contiguous.

Pitfall: Rechecking every prefix or partition from scratch hides an avoidable quadratic loop; maintain an invariant and update only the affected state.

Practice these

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