Chapter 9 — Strings
Source:
src/main/kotlin/string/(plus itsdynamic_programming/,sliding_window/,backtracking/,pattern_matching/subfolders)Master idea: a string is an immutable array of characters, and most string problems are really one of three lenses: counts (anagrams — what matters is multiset equality), patterns (isomorphism — what matters is the shape of the mapping), or structure (prefixes, palindromes, word boundaries — what matters is position).
Prerequisites: hash maps from Chapter 6, two pointers from Chapter 3, and the DP lens from Chapter 2 for the harder variants.
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 9.1 | Valid Anagram | counter array (+1 / -1) | $O(n)$ | → |
| 9.2 | Group Anagrams | frequency-vector key | $O(n \cdot L)$ | → |
| 9.3 | Isomorphic Strings | pattern encoding | $O(n)$ | → |
| 9.4 | Longest Palindromic Substring | expand around center | $O(n^2)$ | → |
| 9.5 | Longest Common Prefix | vertical scan | $O(n \cdot L)$ | → |
| 9.6 | Reverse Words In A String | split + two pointers | $O(n)$ | → |
| 9.7 | Validate IP Address | segment validation | $O(n)$ | → |
| 9.8 | Find The Index Of The First Occurrence | Rabin-Karp rolling hash | $O(n+m)$ | → | | 9.9 | Number Of Matching Subsequences | 26 buckets of word-states | $O(n + W)$ | → | | 9.10 | Find The Index Of The First Occurrence (KMP) | LPS array | $O(n+m)$ | → | | 9.11 | Valid Palindrome | two pointers with skip | $O(n)$ | → | | 9.12 | Count And Say | run-length iteration | $O(\text{term})$ | → | | 9.13 | Add Strings | digit-wise carry | $O(n)$ | → | | 9.14 | String To Integer (atoi) | phase scanner + overflow pre-check | $O(n)$ | → | | 9.15 | Text Justification | greedy pack + space split | $O(nw)$ | → | | 9.16 | Length Of Last Word | backward scan | $O(n)$ | → | | 9.17 | Merge Strings Alternately | max-length loop | $O(n+m)$ | → | | 9.18 | Goat Latin | word transform | $O(n)$ | → | | 9.19 | Detect Capital | capital-count rules | $O(n)$ | → | | 9.20 | Is Subsequence | two-pointer match | $O(|t|)$ | → | | 9.21 | String Compression | in-place run-length | $O(n)$ | → | | 9.22 | Custom Sort String | rank-map sort | $O(n log n)$ | → | | 9.23 | Rank Teams By Votes | position-frequency sort | $O(vn)$ | → | | 9.24 | Valid Palindrome II | skip-one palindrome check | $O(n)$ | → | | 9.25 | String Compression III | 9-capped run-length | $O(n)$ | → | | 9.26 | Happy Number | digit-square cycle | $O(log n)$ | → | | 9.27 | Multiply Strings | digit-by-digit | $O(nm)$ | → | | 9.28 | Add Binary | carry walk | $O(n)$ | → | | 9.29 | Palindrome Number | reverse-half compare | $O(log x)$ | → | | 9.30 | GCD Of Strings | string division | $O(n+m)$ | → | | 9.31 | Valid Number | state-machine scan | $O(n)$ | → | | 9.32 | Valid Word Abbreviation | two-pointer expansion | $O(n)$ | → | | 9.33 | Shortest Way To Form String | greedy scans | $O(mn)$ | → | | 9.34 | Reverse Vowels | two-pointer swap | $O(n)$ | → | | 9.35 | Excel Sheet Column Number | base-26 decode | $O(n)$ | → | | 9.36 | Maximum Value After Insertion | position scan | $O(n)$ | → | | 9.37 | Nested List Weighted Sum | depth DFS | $O(n)$ | → | | 9.38 | Unique Substring With Equal Digit Frequency | prefix-frequency | $O(n^3)$ | → |
The rest of the string/ directory
src/main/kotlin/string/ is huge: more counting/pattern problems (Detect Capital, Isomorphic variants, IsSubsequence, Count Words With A Given Prefix), parsing & validation (Valid Number, Validate IP Address (better implementation), Excel Sheet To Column Number, Count And Say, Goat Latin, String Compression), DP-heavy classics in dynamic_programming/ (Edit Distance, Regular Expression Matching, Interleaving String, Palindrome Partitioning II, Longest Palindromic Subsequence), sliding_window/ (Longest Substring Without Repeating Characters and friends), pattern_matching/, and backtracking/ (Generate Parentheses, Word Break II, Word Square).
New pages are appended to the table above as they’re written.