Advanced Strings Practice Questions
Ten interview problems, every algorithm in the chapter represented. The easy problems are direct applications; the hard ones require combining multiple techniques — if you’re solving them correctly, you’ve genuinely internalized the material.
Before reading any solution, ask yourself:
- Is this a “find pattern in text” problem? → try KMP or Z-algorithm.
- Does it involve duplicate / repeated substrings of a specific length? → try Rabin-Karp rolling hash.
- Does it involve palindromes? → expand-around-center for O(n²), Manacher’s for O(n).
- Does it involve a sliding window with character frequencies? → two-pointer + frequency array.
The code follows from the right framing.
Easy
| Problem | Pattern | Status |
|---|---|---|
| Implement strStr | KMP or naive | Available |
| Repeated Substring Pattern | KMP failure function — period detection | Available |
Medium
| Problem | Pattern | Status |
|---|---|---|
| Longest Happy Prefix | KMP failure function directly | Available |
| Find All Anagrams in a String | Sliding window + frequency array | Available |
| Minimum Window Substring | Sliding window + two-pointer | Available |
| Longest Palindromic Substring | Expand around center / Manacher’s | Available |
| Count and Say | String simulation / run-length encoding | Available |
Hard
| Problem | Pattern | Status |
|---|---|---|
| Shortest Palindrome | KMP on s + '#' + reverse(s) | Available |
| Longest Duplicate Substring | Binary search + Rabin-Karp rolling hash | Available |
| Wildcard Matching | DP (2D) or greedy two-pointer | Available |
More Practice (Coming Soon)
| Problem | Pattern | Status |
|---|---|---|
| Word Search II | Trie + DFS (Aho-Corasick flavor) | Coming Soon |
| Edit Distance | Classic 2D DP | Coming Soon |
| Regular Expression Matching | DP with wildcard semantics | Coming Soon |
| Distinct Subsequences | 2D DP | Coming Soon |
| Text Justification | String simulation | Coming Soon |
| Scramble String | Interval DP | Coming Soon |
| Palindrome Pairs | Trie + KMP | Coming Soon |
| Count Palindromic Substrings | Manacher’s or expand | Coming Soon |
| String to Integer (atoi) | Careful parsing | Coming Soon |
| Decode Ways | 1D DP on digits | Coming Soon |