Strings
Character counting, two pointers and normalisation — the recurring shapes of string problems
Strings are arrays of characters, so most array techniques carry over directly. What makes string problems distinct is that the content often has structure worth exploiting — letters have counts, words have boundaries, and equivalent strings can be reduced to a shared canonical form.
The Patterns
1. Counting — reduce a string to a multiset
Once you only care about which characters and how many, order stops mattering and the problem usually becomes easy.
- Valid Anagram — exact count equality
- Longest Palindrome — pairs plus at most one centre
- Shortest Completing Word — count containment, where a set would be wrong
Sets lose multiplicity
The most common bug in this family is using a set where counts are needed. "step" has an s; it does not have two. If the problem cares how many times something appears, count it.
2. Two pointers — walk from both ends or at different rates
- Valid Palindrome — converging, with skip rules
- Is Subsequence — same direction, one pointer advancing conditionally
- Length of Last Word — scanning backwards in two phases
3. Normalisation — make equivalent strings identical
Rather than asking "are these equivalent?", transform both into a canonical form and ask "are these equal?".
- Unique Email Addresses — apply the rules, then de-duplicate with a set
- Isomorphic Strings — structural equivalence via two maps
- Keyboard Row — map each character to a category
4. Simulation — follow the specification exactly
Some problems have no clever insight; the challenge is holding a fiddly rule set straight.
- Roman to Integer / Integer to Roman — inverse conversions with different techniques
- Zigzag Conversion — a bouncing row index
- Text Justification — three interacting formatting rules
Language Gotchas Worth Memorising
| Situation | Python | TypeScript |
|---|---|---|
| Split on whitespace, dropping empties | s.split() | s.trim().split(/\s+/) |
| Split on a single space (keeps empties) | s.split(" ") | s.split(" ") |
| Reverse a string | s[::-1] | [...s].reverse().join("") |
| Integer division | a // b | Math.floor(a / b) |
| Truncate toward zero | int(a / b) | Math.trunc(a / b) |
| Count characters | Counter(s) | a Map built by hand |
| Missing key returns 0 | Counter[k] | map.get(k) ?? 0 |
Build strings with join, not +=
Repeated result += char inside a loop allocates a new string each iteration — O(n²) overall. Collect pieces in a list and join once.
All Problems
| Problem | Difficulty | Pattern |
|---|---|---|
| Valid Palindrome | Easy | Two Pointers |
| Valid Anagram | Easy | Counting |
| Longest Common Prefix | Easy | Vertical Scan |
| Length of Last Word | Easy | Reverse Scan |
| Roman to Integer | Easy | Local Comparison |
| Is Subsequence | Easy | Two Pointers |
| Isomorphic Strings | Easy | Two Hash Maps |
| Longest Palindrome | Easy | Counting |
| First Occurrence in a String | Easy | String Matching |
| Keyboard Row | Easy | Hash Map |
| Shortest Completing Word | Easy | Counting |
| Unique Email Addresses | Easy | Normalisation |
| Palindrome Number | Easy | Digit Math |
| Integer to Roman | Medium | Greedy |
| Reverse Words in a String | Medium | Two Pointers |
| Zigzag Conversion | Medium | Simulation |
| Text Justification | Hard | Simulation |