String Practice Problems
How to Use This Problem List
String problems are deceptive. They look different on the surface but almost all of them reduce to one of six patterns. The goal of practice is not to memorize solutions — it is to build pattern recognition fast enough that you identify the approach within two minutes of reading the problem.
The best way to use this list: pick one pattern, solve every problem in that section before moving to the next. After three or four problems in a pattern, the recognition becomes automatic. Jumping between patterns at random slows this process down.
For each problem, spend the first five minutes identifying the pattern before writing any code. If you cannot identify it, read the key insight hint — it names the technique without giving the implementation. That hint alone should be enough to unlock the approach.
Pattern 1: Two Pointers
These problems use two indices that move toward each other or in the same direction. The key is knowing when to move each pointer and what invariant to maintain between them.
| Problem | Difficulty | Key Insight |
|---|---|---|
| Valid Palindrome | Easy | Skip non-alphanumeric, compare case-insensitive from both ends |
| Reverse String | Easy | Swap outermost characters, converge inward |
| Reverse Vowels of a String | Easy | Two pointers scan inward, swap only when both point to vowels |
| Valid Palindrome II | Medium | One deletion allowed — try skipping left or right, check both remainders |
| Palindrome Linked List | Medium | Find middle, reverse second half, compare from both ends |
| Strobogrammatic Number | Medium | Two pointers, valid pairs are (0,0)(1,1)(6,9)(8,8)(9,6) |
| Minimum Number of Moves to Make Palindrome | Hard | Count swaps needed to make each position symmetric |
Complexity target: O(n) time, O(1) space for most. O(n) space only when you must convert to a mutable structure.
Pattern 2: Frequency Count
These problems compare character distributions — who appears, how often, whether two strings have the same multiset of characters. Build a frequency table once, query in O(1).
| Problem | Difficulty | Key Insight |
|---|---|---|
| Valid Anagram | Easy | Increment for first string, decrement for second — check all-zeros |
| Ransom Note | Easy | Frequency of magazine must cover frequency of note |
| First Unique Character in a String | Easy | Two-pass — build freq, then scan for first with freq == 1 |
| Find the Difference | Easy | XOR all characters — the extra one remains |
| Sort Characters By Frequency | Medium | Count freq, sort by count descending, rebuild string |
| Minimum Number of Steps to Make Two Strings Anagram | Medium | Count how many chars in one string are absent from the other |
| Find All Anagrams in a String | Medium | Fixed sliding window — compare window freq to pattern freq |
| Palindrome Permutation | Easy | Count chars with odd frequency — must be ≤ 1 |
| Group Anagrams | Medium | Frequency array as hash map key — group by canonical form |
| Character Replacement | Medium | Window valid while (length - maxFreq) ≤ k |
| Top K Frequent Words | Medium | Frequency map, then sort by count (and lexicographically) |
Complexity target: O(n) time. O(1) space for fixed alphabet (int[26]). O(k) for hash map where k = distinct chars.
Pattern 3: Sliding Window
These problems ask for the longest, shortest, or count of contiguous substrings satisfying a condition. Expand right to grow the window, shrink left to restore validity.
| Problem | Difficulty | Key Insight |
|---|---|---|
| Longest Substring Without Repeating Characters | Medium | Hash set tracks window — shrink left on any duplicate |
| Minimum Size Subarray Sum | Medium | Shrink left while sum ≥ target, track minimum length |
| Longest Substring with At Most K Distinct Characters | Medium | Hash map of window counts — shrink when distinct > k |
| Longest Repeating Character Replacement | Medium | Window valid while (length - maxFreq) ≤ k |
| Find All Anagrams in a String | Medium | Fixed window size = pattern length — compare freq arrays |
| Permutation in String | Medium | Fixed window — check if window is a permutation of pattern |
| Minimum Window Substring | Hard | Variable window — track how many pattern chars are satisfied |
| Substring with Concatenation of All Words | Hard | Fixed window of word count × word length — check permutation |
| Sliding Window Maximum | Hard | Monotonic deque maintains max in O(1) per slide |
| Count Distinct Characters in All Substrings | Hard | Each char contributes independently — count its span |
Complexity target: O(n + m) time where m = pattern length. O(k) space for window structure.
Pattern 4: Expand Around Center
These problems involve palindromic substrings — finding the longest, counting all of them, or partitioning around them. Every palindrome has a center — expand outward from each possible center.
| Problem | Difficulty | Key Insight |
|---|---|---|
| Longest Palindromic Substring | Medium | Expand from each of 2n-1 centers — track longest bounds |
| Count Palindromic Substrings | Medium | Same expansion — count each valid step rather than tracking longest |
| Palindrome Partitioning | Medium | Backtrack — precompute palindrome table or expand on the fly |
| Palindrome Partitioning II | Hard | DP — min cuts using precomputed palindrome boolean table |
| Valid Palindrome (full string) | Easy | Single expansion or two pointers — simpler than substring |
| Longest Palindromic Subsequence | Medium | DP — different from substring (need not be contiguous) |
| Minimum Insertions to Make String Palindrome | Medium | DP — related to longest palindromic subsequence |
Complexity target: O(n²) time for expansion-based approaches. O(1) space (indices only). DP approaches are O(n²) time and O(n²) space.
Pattern 5: String Building and Transformation
These problems construct a new string by filtering, replacing, or rearranging characters from the input. The output is assembled character by character under a rule. Always build into a mutable buffer — never concatenate with + in a loop.
| Problem | Difficulty | Key Insight |
|---|---|---|
| Reverse Words in a String | Medium | Split on whitespace, reverse word array, join |
| Reverse Words in a String III | Easy | Split, reverse each word individually, join |
| Remove Vowels from a String | Easy | Filter — append only non-vowels to StringBuilder |
| Remove All Adjacent Duplicates | Easy | Stack — push if different from top, pop if same |
| Decode String | Medium | Stack stores (count, prefix) — process inner brackets first |
| String Compression | Medium | Two pointers — write pointer and read pointer counting runs |
| Add Strings (no arithmetic) | Easy | Process digit by digit from right, carry the overflow |
| Multiply Strings | Medium | Grade-school multiplication on digit arrays |
| Simplify Unix Path | Medium | Split on '/', stack handles '..' — join with '/' |
| Remove Duplicate Letters | Medium | Greedy + stack — maintain lexicographically smallest result |
Complexity target: O(n) time. O(n) space for the output buffer.
Pattern 6: Hash Map and Canonical Form
These problems group, match, or compare strings based on structure rather than literal content — isomorphic strings, word patterns, finding strings with the same shape.
| Problem | Difficulty | Key Insight |
|---|---|---|
| Isomorphic Strings | Easy | Bidirectional map — both char→char must be consistent |
| Word Pattern | Easy | Bidirectional map — both char→word and word→char |
| Find and Replace Pattern | Medium | Encode each string as sequence of first-occurrence indices |
| Group Shifted Strings | Medium | Canonical form = difference sequence of char shifts |
| Unique Word Abbreviation | Medium | Hash map of abbreviation → set of words |
| Longest Word in Dictionary through Deleting | Medium | Check if word is subsequence of string |
| Custom Sort String | Medium | Sort second string by character order defined in first |
Complexity target: O(n × k) time where n = number of strings, k = average length. O(n × k) space for map storage.
Pattern 7: Search and Matching
These problems search for a pattern inside a text — single occurrence, all occurrences, or structural matches. Know the complexity difference between naive search (O(n × m)) and KMP (O(n + m)).
| Problem | Difficulty | Key Insight |
|---|---|---|
| Implement strStr (indexOf) | Easy | Naive O(n × m) — sufficient for interview if stated explicitly |
| Repeated Substring Pattern | Easy | If s is in (s+s)[1:-1], then s has a repeated pattern |
| Find the Index of the First Occurrence | Easy | KMP avoids re-checking characters — O(n + m) |
| Shortest Palindrome | Hard | Find longest palindromic prefix using KMP failure function |
| Longest Happy Prefix | Hard | KMP failure function directly gives the answer |
| Count Occurrences of Anagrams | Medium | Fixed sliding window with frequency comparison |
Complexity target: O(n) for simple cases. O(n + m) with KMP. O(n × m) naive — always state which you are using.
Pattern 8: Number and String Conversion
These problems sit at the boundary between string manipulation and arithmetic — converting between representations, parsing, or simulating numeric operations on strings.
| Problem | Difficulty | Key Insight |
|---|---|---|
| String to Integer (atoi) | Medium | Handle whitespace, sign, overflow, non-digit termination in order |
| Integer to Roman | Medium | Greedy — always use the largest denomination that fits |
| Roman to Integer | Easy | Process left to right — if current < next, subtract; else add |
| Excel Sheet Column Number | Easy | Base-26 conversion — 'A'=1, 'Z'=26, 'AA'=27 |
| Excel Sheet Column Title | Easy | Reverse base-26 — handle the offset (1-indexed, not 0-indexed) |
| Valid Number | Hard | State machine or regex — cover all cases: sign, digits, dot, exponent |
| Reverse Integer | Medium | Build reversed string, check overflow before converting |
Complexity target: O(n) where n = number of characters in the string.
Recommended Study Order
Week 1 — Core Patterns Pattern 2 (Frequency Count): Valid Anagram, First Unique Char, Ransom Note Pattern 1 (Two Pointers): Valid Palindrome, Reverse String, Reverse Vowels Week 2 — Sliding Window and Building Pattern 3 (Sliding Window): Longest Without Repeating, Permutation in String Pattern 5 (Build Result): Reverse Words, Remove Duplicates, String Compression Week 3 — Palindromes and Structure Pattern 4 (Expand Center): Longest Palindromic Substring, Count Palindromes Pattern 6 (Hash Map): Isomorphic Strings, Word Pattern, Group Anagrams Week 4 — Search and Conversion Pattern 7 (Search): Repeated Substring, strStr, Count Anagrams Pattern 8 (Conversion): atoi, Roman to Integer, Excel Column Revisit anything that felt weak
Problem-Solving Checklist
Before writing any code, run through this for every string problem:
1. What varies with n? → n = string length? n = number of strings? m = pattern length? → Separate variables before estimating complexity. 2. What is the character set? → Lowercase only → int[26] array, O(1) space → ASCII → int[128] array, O(1) space → Unicode → hash map, O(k) space 3. Does order matter? → Yes → sliding window, two pointers, build result → No → frequency count, sorting, canonical form 4. Is contiguity required? → Substring → sliding window or expand center → Subsequence → DP or two pointers in order 5. What is the output shape? → Boolean → usually check or compare → Integer (count/length) → track running max/min/count → String → build result into mutable buffer 6. What is the brute force and its bottleneck? → Name the bottleneck before optimizing → Every nested loop over pairs of characters → O(n²) → Every substring creation in a loop → O(n³) 7. Edge cases to check: → Empty string → loop never executes, defaults correct? → Single character → two-pointer stops immediately → All same characters → frequency array all in one slot → No match found → return -1 / null / empty string / 0
Difficulty Progression Reference
| Stage | What It Looks Like | Representative Problems |
|---|---|---|
| Foundation | Single pass, one variable, basic char checks | Valid Anagram, Reverse String, First Unique Char |
| Early Intermediate | Two pointers or fixed window, one pattern applied cleanly | Valid Palindrome, Find All Anagrams, Permutation in String |
| Intermediate | Combining frequency + window, or expand-center | Longest Substring No Repeat, Longest Palindromic Substring |
| Late Intermediate | Multi-step transforms, variable window, stack-based build | Min Window Substring, Decode String, Remove Duplicate Letters |
| Advanced | KMP, DP on strings, hard constraint combinations | Shortest Palindrome, Palindrome Partitioning II, Valid Number |
Company Focus Reference
Product-based companies (FAANG-tier):
- ›Sliding window substring problems appear very frequently
- ›Anagram and frequency problems — especially the harder variants
- ›Palindrome partitioning and counting
- ›String encoding/compression and decode
Service-based and on-campus interviews:
- ›Valid palindrome, reverse words, anagram check
- ›String to integer (atoi), Roman numeral conversions
- ›Basic sliding window at easy-medium level
Startup and mid-size tech:
- ›Practical string manipulation — split, build, compress
- ›Word pattern and isomorphic strings
- ›Sliding window at medium level with clear constraints
Progress Tracking
After solving each problem, record:
- ›Pattern used — which of the 8 patterns above does this belong to?
- ›Recognition clue — what phrase or constraint told you which pattern to use?
- ›Edge case missed — what input broke your first attempt?
- ›Time taken — target 20-25 minutes for medium problems under interview conditions
After 25-30 problems, review your notes. You will see clearly which patterns you recognize instantly and which still require the hint. Focus the next session entirely on those weak patterns.
The signal that you are ready for interviews: you can name the pattern within two minutes of reading any new string problem, even one you have never seen before.