String Patterns
String questions are array questions with a smaller alphabet, and that smaller alphabet is the whole opportunity. Because there are only twenty-six lowercase letters, a frequency count fits in a fixed array and comparing two counts is a constant-time operation. Most string interview problems are a sliding window over a frequency map, a palindrome expanded from its centre, or a table comparing two sequences.
Where to start, and what comes next
- 01
Hashing / Frequency Map
Frequency counting is the foundation. Anagrams, character counts and grouping all reduce to it, and the fixed 26-slot array is the trick that makes it constant time.
- 02
Sliding Window on String
The array window, now over characters, with a frequency map as the window state. This covers a large share of the medium-difficulty string set.
- 03
Palindrome Patterns
Expand around centre first, which is O(n squared) and easy to reason about, before meeting Manacher's linear version.
- 04
String DP
Edit distance and longest common subsequence. Two sequences means a two-dimensional table, and this is the cleanest place to learn that shape.
- 05
Pattern Matching
KMP and the Z-algorithm. Rarely required outright, but the failure function is a genuinely different idea and is worth understanding once.
If you only have time for three things
- Frequency counting with a fixed 26-slot array, and knowing when to switch to a HashMap because the input is not plain lowercase ASCII.
- The variable-size window with a counter tracking how many requirements are satisfied, which turns validity into an O(1) check.
- Expand around centre, including the detail that there are 2n-1 centres because even-length palindromes are centred between two characters.
Ask about the character set before writing anything. Whether the input is lowercase ASCII, mixed case, or Unicode decides between a 26-slot array and a map, and asking shows you noticed. In Java, also be ready for the point that repeated concatenation in a loop is quadratic because strings are immutable, which is why StringBuilder exists.
The idea underneath
Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).
Problems that use these patterns
Head to head
Questions people ask
Why 26 slots rather than a HashMap?
An array indexed by the character minus 'a' has no hashing, no boxing and no allocation, so it is meaningfully faster and comparing two of them is a fixed-cost operation. It only works if the input really is lowercase a to z, which is worth confirming rather than assuming.
Is Manacher's algorithm expected?
Rarely. Expand around centre at O(n squared) is the expected answer for longest palindromic substring, and knowing that a linear algorithm exists is usually enough. Being asked to implement Manacher's from scratch is uncommon outside competitive programming.
Why is string concatenation in a loop a problem in Java?
Strings are immutable, so each concatenation allocates a new string and copies the old contents. Doing that n times is O(n squared) in total. StringBuilder appends into a resizable buffer instead, making the loop linear.