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.
What a String Actually Is
A string is an array whose slots hold characters. Everything you know about arrays applies — index access is O(1), insertion in the middle is O(n).
But one property changes how you write the code, in both languages used here.
Strings are immutable
You cannot change a character in place. word[0] = "H" fails in Python and silently does nothing in JavaScript.
Every "modification" builds a whole new string, copying every character:
s = "hello"
s = s + "!" ← does NOT append.
Allocates a new 6-character string,
copies all of "hello" into it, adds "!"The performance trap this creates
Building a string inside a loop with += copies everything built so far, every single time.
Building an n-character string with += :
step 1 copies 1 char, step 2 copies 2, step 3 copies 3 …
total ≈ n²/2 character copies → O(n²)At 100,000 characters that is five billion copies. The fix is the same idea in both languages: collect the pieces in a list, then join once at the end.
Slow — O(n²) | Fast — O(n) | |
|---|---|---|
| Python | s += c in a loop | parts.append(c) … "".join(parts) |
| TypeScript | s += c in a loop | parts.push(c) … parts.join("") |
A list is mutable, so appending to it is genuinely cheap. Only the final join allocates.
Characters are numbers
Each character has a numeric code. That is what makes counting tricks work:
'a' = 97, 'b' = 98, … 'z' = 122
ord(c) - ord('a') → 0 for 'a', 1 for 'b', … 25 for 'z'So a 26-slot array can count letters, using the letter itself to pick the slot — no hash map needed, and no hashing cost. This is the basis of most anagram and frequency problems below.
Two habits worth forming early
Say which alphabet you assume. "Lowercase English letters only" makes a 26-slot array correct. Without that guarantee, use a hash map — real text contains accents, emoji and capitals.
Case and whitespace are decisions, not details. Is "Hello" equal to "hello"? Does a trailing space matter? Problems that hinge on this rarely say so directly, and getting it wrong looks like a logic bug.
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 |