Arrays, Strings, Hashing, And Two Pointers

What's being tested

These problems test hashing, two pointers, sliding-window reasoning, and careful string parsing over arrays and text. Strong solutions identify whether order, contiguity, duplicates, circular indexing, or exact token boundaries determine the appropriate O(n) or O(n log n) strategy.

Patterns & templates

• Two pointers on sorted arrays — move the left pointer upward or right pointer downward based on the sum; handle duplicates deliberately.

• Hash maps and sets — track frequencies, last-seen positions, or distinct characters for linear-time substring and pair-counting solutions.

• Contribution counting — count how many substrings include each character’s unique contribution instead of enumerating all O(n²) substrings.

• Prefix sums for circular distances — duplicate or modularize indices, then compute interval distance as prefix[r] - prefix[l].

• Monotonic boundary scans — find the first inversion from the left and right, expand around the unsorted region, then validate the repaired range.

• Finite-state parsing — recognize complete price tokens using character boundaries; avoid matching $12 inside $123 or unrelated text.

• Complexity discipline — prefer O(n) time and O(n) space; use sorting only when its O(n log n) cost simplifies correctness and duplicate handling.

Common pitfalls

Pitfall: Treating circular routes like linear arrays; compare clockwise and counterclockwise distances and normalize with modulo.

Pitfall: Counting distinct substring spellings rather than occurrences by position, or accidentally using 32-bit arithmetic for large totals.

Pitfall: Moving both two-pointer indices after every match without grouping duplicates, causing missed pairs or repeated output.

Practice these

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