Strings - KMP, Rabin-Karp, Pattern Matching & More

Strings — Immutability, Creation & Manipulation

“

Strings — Immutability & Memory

Strings are IMMUTABLE — every transform creates a new object String Pool (JVM): val a = "hello" ─┐ val b = "hello" ─┤──→ [same pooled object] │ a === b ✓ true val c = StringBuilder("hello").toString() └──→ [new object] a === c ✗ false a == c ✓ true

Thread-safe: no synchronization needed — immutable data can't be corrupted
Always use == (structural equality) — never === (referential) for strings
equals(other, ignoreCase = true) for case-insensitive comparison
Concatenation in loops is O(n²) — use StringBuilder instead → O(n)

✎

Creating & Comparing Strings

// ── Creation ── val s = "Hello" val fromChars = charArrayOf('H','i').concatToString() chars.concatToString(1, 4) // startIndex, endIndex val fromNum = 42.toString() // "42" val hex = 255.toString(16) // "ff" val bin = 10.toString(2) // "1010" val dashes = "-".repeat(20) // ── Templates ── "Name: $name, Len: ${name.length}" // ── Comparison ── a == b // content a.equals(b, ignoreCase = true) a.compareTo(b) // -/0/+ a.compareTo(b, ignoreCase = true) // Case-insensitive sort words.sortedWith(String.CASE_INSENSITIVE_ORDER) // ── Multi-line ── val ml = """ Line 1 Line 2 """.trimIndent()

🔍

String Inspection & Navigation

val s = "Hello, World!" // ── Length & Checks ── s.length s.isEmpty() s.isBlank() // ── Char access — O(1) ── s[0] s.first() s.last() s.getOrNull(100) // null // ── Substring checks ── s.startsWith("Hello") s.endsWith("!") s.contains("World") "world" in s // false (case-sensitive) s.contains("world", ignoreCase = true) // ── Index of ── s.indexOf('o') // 4 (first) s.lastIndexOf('o') // 8 (last) s.indexOf('o', startIndex = 5)

✦

String Transformation

// ── Case ── s.uppercase() s.lowercase() // ── Substrings ── s.substring(7) // "World!" s.substring(7, 12) // "World" s.take(5) s.drop(7) s.substringBefore(",") // "Hello" s.substringAfter(", ") // "World!" // ── Replace & Remove ── s.replace("Hello", "Hi") s.replaceFirst("l", "L") s.filter { it.isLetter() } s.removePrefix("https://") s.removeSuffix(".kt") // ── Trim & Pad ── s.trim() s.trimStart() s.trimEnd() "42".padStart(5, '0') // "00042" // ── Reversed ── s.reversed() // "!dlroW ,olleH"

✂

Splitting, Joining & Formatting

// ── Split ── "a,b,c".split(",") // [a, b, c] "a,b,c".split(",", limit=2) // [a, b,c] "one two".split(Regex("\\s+")) "hello".toList() // [h,e,l,l,o] "hello".toCharArray() // mutable "abcdef".chunked(3) // [abc, def] "abcde".windowed(3) // [abc,bcd,cde] "abcde".windowed(3, step=2) // [abc,cde] "line1\nline2".lines() // [line1, line2] // ── Join ── listOf("a","b").joinToString(", ") words.joinToString("|", prefix="[", postfix="]") words.joinTo(sb, ", ") // append to SB // ── Format ── "%.2f".format(3.14159) // "3.14"

⚒

StringBuilder — Mutable Strings

String concat in loop = O(n²): result += "x" → copies all prev chars each time iter k copies k chars → total = 1+2+...+n = O(n²) StringBuilder = O(n): mutable buffer, O(1) amortized append single .toString() copy at the end

val sb = StringBuilder(256) // pre-alloc sb.append("Hello").append(", ") sb.appendLine("World") sb.insert(0, ">>>") // O(n) shift sb.delete(0, 3) // O(n) sb.reverse() // in-place sb[0] = 'H' // O(1) val result = sb.toString() sb.clear() // clear & reuse // Kotlin DSL val s = buildString { append("hi") }

Character Properties & Arithmetic

// ── Type Checks ── 'A'.isLetter() '5'.isDigit() ' '.isWhitespace() 'A'.isUpperCase() 'a'.isLowerCase() // ── Conversion ── 'a'.uppercaseChar() // 'A' '7'.digitToInt() // 7 'f'.digitToInt(16) // 15 // ── Arithmetic ── 'e' - 'a' // 4 (Int offset) 'a' + 4 // 'e' (Char) '7' - '0' // 7 (digit → int) // ── Frequency array (lowercase) ── val freq = IntArray(26) for (ch in str) freq[ch - 'a']++

✱

Regular Expressions

val digits = Regex("\\d+") // Match entire string digits.matches("12345") // true // Partial match digits.containsMatchIn("abc123") // Find first / all digits.find("price: 42")?.value // "42" digits.findAll("1 cat 34 birds") .map { it.value } // [1, 34] // Replace digits.replace("a1b2", "*") // "a*b*" // Groups val r = Regex("(\\d{4})-(\\d{2})") val m = r.find("2026-03") m?.groupValues // [2026-03, 2026, 03] // Split by regex "one1two22three".split(Regex("\\d+"))

Algorithm Patterns for Strings

See Also: Arrays Page

Several array algorithm patterns apply directly to string problems: Two Pointers → palindrome check, reverse string | Sliding Window → longest substring without repeating chars, minimum window substring | Frequency Counting → anagram detection, character frequency | Prefix Sums → substring hash precomputation

≣

KMP & Rabin-Karp — String Matching

O(n+m) O(m)

KMP (Knuth-Morris-Pratt) Build failure function (LPS array): pattern: A B A B C LPS: [0 0 1 2 0] ↑ longest proper prefix = suffix text: A B A B D A B A B C pat: A B A B C ← mismatch at C LPS[3]=2 → shift, don't restart! text: A B A B D A B A B C pat: A B A B C ← resume at LPS value Key: Never re-examine matched text chars → O(n+m) guaranteed

Rabin-Karp (Rolling Hash) Compute hash of pattern & sliding window: pattern: "ABC" hash=h(ABC) text: [A B C] D E F A B C hash₁=h(ABC) → match! verify chars Rolling update: hash₂ = (hash₁ - A·d²) · d + D remove oldest, shift, add newest → O(1) per slide text: A [B C D] E F A B C hash₂≠h(ABC) → skip Key: Hash collisions require char-by-char verify → worst O(nm), avg O(n+m)

When to Use

substring searchWhy: Naive search is O(n·m) — backtracking on mismatch. KMP uses the failure function to skip ahead: partial matches tell you where to resume. Rabin-Karp uses rolling hash to check windows in O(1). Both achieve O(n+m). pattern occurrencesWhy: Find ALL occurrences of a pattern in text. KMP continues scanning after each match using the LPS array. Rabin-Karp slides the hash window. Both handle overlapping matches naturally and count all instances in O(n+m). repeated substring patternWhy: "Does string s consist of a repeated pattern?" Build the KMP failure table. If n % (n - LPS[n-1]) == 0, the string is built from repeating the prefix of length (n - LPS[n-1]). One LPS build, O(n). string rotationWhy: Check if B is a rotation of A by searching for B in A+A using KMP. If B appears as a substring of the doubled text, it's a rotation. Reduces rotation-check to substring search — O(n) with KMP instead of checking all n rotations naively at O(n²). multi-pattern searchWhy: Rabin-Karp excels here: compute hashes for ALL patterns, then slide once over text checking against the hash set. Average O(n·k) for k patterns vs O(n·m·k) naive. Aho-Corasick is optimal at O(n+m) for this. shortest palindromeWhy: Find the longest palindromic prefix using KMP. Build LPS for (s + "#" + reversed s). The LPS value at the end tells you how much of the prefix is already a palindrome. Prepend the rest reversed. O(n). longest happy prefixWhy: Longest proper prefix that is also a suffix = exactly what the KMP failure function computes. LPS[n-1] gives the answer length directly. Single LPS build, O(n).

KMP: Build LPS (failure function) in O(m), then match in O(n) — worst case O(n+m)
Rabin-Karp: Rolling hash with modular arithmetic — average O(n+m), worst O(nm)
KMP advantage: guaranteed O(n+m); Rabin-Karp advantage: simpler, multi-pattern
LPS[i]: length of longest proper prefix of pattern[0..i] that is also a suffix
Kotlin: text.indexOf(pattern) uses naive search — KMP needed for O(n+m) guarantee

▶ Visualize

Common Pitfalls & Gotchas

⚠

String & Iteration Traps

// WRONG: O(n²) string concat in loop var r = "" for (i in 0 until n) r += "x" // RIGHT: O(n) with StringBuilder val sb = StringBuilder() for (i in 0 until n) sb.append("x") // WRONG: ConcurrentModificationException for (x in list) if (x % 2 == 0) list.remove(x) // RIGHT: list.removeAll { it % 2 == 0 }

s.length counts UTF-16 code units, not characters — many emoji = 2+ Chars (surrogate pairs)
Unicode-correct count: s.codePointCount(0, s.length) — counts actual characters
replace() replaces all occurrences; use replaceFirst() for just the first
split(",") returns List<String>, not array — use .toTypedArray() if needed

Quick Reference

⚡

Algorithm Complexity at a Glance

Algorithm	Time	Space	Key Requirement
Two Pointers (converge)	`O(n)`	`O(1)`	Palindrome check, reverse string
Sliding Window (variable)	`O(n)`	`O(k)`	Longest substring with constraint
Frequency Counting	`O(n)`	`O(k)`	Anagram detection, char frequency
KMP String Match	`O(n+m)`	`O(m)`	Pattern search with failure function
Rabin-Karp	`O(n+m) avg`	`O(1)`	Rolling hash substring search

✨

Which Pattern?

If You See...	Try This
"palindrome" / "reverse string"	Two Pointers (converge)
"longest substring" with constraint	Sliding Window (variable)
"anagram" / "frequency" / "unique chars"	Frequency Counting
"minimum window substring"	Sliding Window + Frequency
"find pattern in text" / "substring"	KMP / Rabin-Karp
"repeated pattern" in string	KMP (LPS array)
"permutation in string"	Sliding Window (fixed) + Freq

Data Structure Operations

☰

String & StringBuilder Operations — Complexity

Operation	String	StringBuilder	Notes
Access by index	`O(1)`	`O(1)`	`s[i]` / `sb[i]`
Update by index	immutable	`O(1)`	`sb[i] = 'x'`
Append	`O(n)` new obj	`O(1)` amortized	`sb.append()`
Insert at index	`O(n)` new obj	`O(n)` shift	`sb.insert(i, str)`
Delete range	`O(n)` new obj	`O(n)` shift	`sb.delete(start, end)`
Substring	`O(k)`	`O(k)`	k = substring length
Reverse	`O(n)` new obj	`O(n)` in-place	`sb.reverse()`
Search (indexOf)	`O(n·m)`	`O(n·m)`	Naive; KMP for O(n+m)
Concatenation	`O(n+m)`	`O(m)` amortized	String creates new object each time
Length	`O(1)`	`O(1)`	Stored as field

Strings — The Complete Visual Reference