Arrays, Strings, Hash Maps, And Sliding Windows

What's being tested

These problems test linear-time string/array processing using hash maps, two pointers, and sliding windows. Interviewers are probing whether you can turn brute-force substring/subarray enumeration into O(n) or O(n log n) solutions while handling edge cases cleanly.

Patterns & templates

• Frequency map with dict / HashMap — count characters, words, or digit encodings; compare counts instead of repeatedly scanning substrings.

• Sliding window over contiguous substrings — expand right, update state, contract left while valid; typical O(n) time and O(k) space.

• Minimum window substring — maintain need, have, and formed; update answer only when all required frequencies are satisfied.

• Two-pointer string scan — use left/right indices for sanitized palindrome checks; skip non-alphanumeric characters before comparing normalized values.

• Kadane’s algorithm for max subarray sum — track bestEndingHere and bestSoFar; initialize with first element to handle all-negative arrays.

• Max product subarray — track both maxEndingHere and minEndingHere because multiplying by a negative flips extremes.

• Canonical encoding — map letters to phone digits or normalized signatures, then group collisions with Map<signature, List<String>>.

Common pitfalls

Pitfall: Recomputing substring counts inside nested loops turns an intended O(n) sliding-window solution into O(n^2 * alphabet).

Pitfall: Treating “valid window” as set containment instead of frequency containment breaks cases with repeated characters like AABC.

Pitfall: Forgetting empty strings, single-character strings, Unicode casing, all-negative arrays, zeros in product arrays, and duplicate grouped keys.

Practice these

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