String Manipulation and Pattern Matching

Strings are arrays of characters, but interviews test extra ideas: immutability, character-set assumptions, and efficient substring search. Knowing when naive matching is fine and when to reach for KMP or Rabin-Karp separates strong candidates.

The core idea

• Immutability: in Java/Python, strings are immutable, so building one char-by-char with + is O(n²). Use a StringBuilder / list-join for O(n).
• Pattern matching: find pattern P (length m) in text T (length n). Naive sliding compare is O(n·m). KMP pre-builds a longest-prefix-suffix (LPS) array so it never re-examines text characters → O(n+m). Rabin-Karp uses a rolling hash for O(n+m) average (O(n·m) worst on collisions) and shines for multi-pattern search.

Algorithm	Time	Space	Best for
Naive match	O(n·m)	O(1)	tiny inputs
KMP	O(n+m)	O(m)	single pattern, guaranteed
Rabin-Karp	O(n+m) avg	O(1)	multiple patterns / avg case
Build string with +	O(n²)	O(n)	avoid!
StringBuilder append	O(n)	O(n)	correct way

Exam Tricks & Tips

• 🎯 Never concatenate in a loop with + — switch to StringBuilder/join to drop O(n²) → O(n).
• 🎯 Anagram / permutation checks → compare 26-length frequency arrays in O(n).
• 🎯 KMP's LPS[i] = length of the longest proper prefix that is also a suffix of P[0..i].
• 🎯 Rabin-Karp: use a rolling hash and verify on hash-match to avoid false positives.
• 🎯 Palindrome checks: two pointers from both ends, O(n)/O(1).
• ❌ Common mistake: assuming 26 lowercase ASCII — clarify Unicode / case / spaces before sizing a count array.

Expected pattern

Substring search, anagram grouping, palindrome/rotation checks, or "implement strStr". Interviewers watch for the immutability trap and whether you can name an O(n+m) matcher.

Quick recap

Treat strings as char arrays but respect immutability (build in O(n), not O(n²)). Naive search is O(n·m); KMP guarantees O(n+m) via the LPS array; Rabin-Karp gives O(n+m) average with a rolling hash. Frequency arrays solve anagram problems in O(n).

Cover the answer, recall, then check. 11 cards on string manipulation and pattern matching.

Q1. Why is building a string with + in a loop slow?
A1. Strings are immutable; each + copies the whole string → O(n²). Use StringBuilder / join for O(n).

Q2. Naive substring search complexity?
A2. O(n·m) — for each of n text positions, compare up to m pattern chars.

Q3. KMP time and space?
A3. O(n+m) time, O(m) space for the LPS (failure) array.

Q4. What does LPS[i] represent in KMP?
A4. The length of the longest proper prefix of the pattern that is also a suffix of P[0..i].

Q5. Why does KMP never re-scan text characters?
A5. On a mismatch it shifts the pattern using LPS instead of restarting, so the text pointer only advances.

Q6. Rabin-Karp average vs worst case?
A6. O(n+m) average with a rolling hash; O(n·m) worst if many hash collisions force full verifications.

Q7. Best matcher for searching many patterns at once?
A7. Rabin-Karp (compare rolling hashes against a set), or Aho-Corasick for large pattern sets.

Q8. Check two strings are anagrams in O(n)?
A8. Compare character-frequency counts (e.g., a 26-length array for lowercase); equal counts ⇒ anagrams.

Q9. Detect if one string is a rotation of another?
A9. Check equal length, then whether (s1 + s1) contains s2 — O(n) with a good matcher.

Q10. Palindrome check complexity?
A10. O(n) time, O(1) space using two pointers moving inward.

Q11. Key clarifying question before sizing a frequency array?
A11. The character set — lowercase (26), full ASCII (128/256), or Unicode, plus case/space handling.

Strings are just arrays of characters, but interviewers layer immutability, character-set tricks and substring search on top. Knowing the costs of common operations — and one linear-time search algorithm — separates a confident answer from a quadratic one.

Core idea: treat a string as an indexable char array, but remember that in many languages (Java, Python, C#) strings are immutable — every "modification" builds a new string. Naive concatenation in a loop is the number-one hidden O(n²).

How it works

Beginner — costs you must know

• Index/compare a char: O(1).
• Length: O(1) (cached).
• Concatenation s + t: O(|s| + |t|) — it copies both. Building a string by += in a loop of n chars is O(n²); use a mutable builder (StringBuilder, list-then-join) for O(n).
• Reverse, lowercase, character-frequency scan: O(n).

Intermediate — the frequency-array trick

For lowercase-English problems, a size-26 integer array beats a hash map on constant factors. Anagram check, "first unique character", and character counting all reduce to: count in one pass, compare/scan in another → O(n) time, O(1) space (26 is constant).

Advanced — substring search

Finding pattern P (length m) in text T (length n):

• Naive: try every start position, compare up to m chars → O(n·m) worst case (e.g. "aaaa…ab" in "aaaa…a").
• KMP (Knuth–Morris–Pratt): precompute a "failure/LPS" table of P in O(m) so that on a mismatch you shift P by the longest proper prefix that is also a suffix — never re-reading text characters. Total O(n + m) time, O(m) space. The key insight: the LPS table remembers how much of P already matched, so the text pointer never moves backward.
• Rabin–Karp: hash a rolling window of T and compare hashes — average O(n + m), useful for multiple-pattern search.

Worked example

Are "listen" and "silent" anagrams? Build a 26-array from "listen": l,i,s,t,e,n each +1. Subtract "silent": each returns to 0. All zero → anagram. Two O(n) passes, O(1) space. Compare this to sorting both strings — that works too but costs O(n log n).

When to use it

• Frequency array: anagrams, permutations-in-string, character counts (fixed small alphabet).
• Two pointers: palindromes, reversing words, in-place edits on a char array.
• KMP / rolling hash: "does P occur in T", repeated-substring, longest-prefix-suffix.

Tricks & gotchas

• Never += strings in a loop — accumulate in a list/builder and join once.
• char - 'a' maps a lowercase letter to index 0–25; watch for uppercase, digits, spaces.
• Palindrome and reversal problems are two-pointer problems in disguise.
• Mnemonic: "Immutable strings punish loops — build, don't append."

Key complexities

• Naive matching: O(n·m); KMP: O(n + m) using the prefix (failure) function.
• Rabin–Karp: O(n + m) average with rolling hash, O(n·m) worst.
• Z-algorithm: O(n); building a suffix array: O(n log n).
• Number of substrings of length-n string: n(n+1)/2.
• LCS / edit distance between lengths m, n: O(m·n) DP.
• String concatenation/immutability: naive building is O(n²); use a builder for O(n).

Usage: use KMP/Z for linear matching; O(mn) DP for string similarity.

Worked Example

Problem: How many times does the pattern "AABAA" occur in the text "AABAACAABAA" (overlaps allowed)? Use naive matching.

Solution: Naive matching slides the pattern (length m = 5) across the text (length n = 11) and checks for a full match at each start position i from 0 to n − m = 6.

• i = 0: text[0..4] = "AABAA" → matches ✓
• i = 1: text[1..5] = "ABAAC" → no
• i = 2..5: "BAACA", "AACAA", "ACAAB", "CAABA" → no
• i = 6: text[6..10] = "AABAA" → matches ✓

Two starting positions (0 and 6) give a full match.

The naive method compares up to m characters at each of ~n positions → O(n·m) worst case (KMP improves this to O(n + m)).

Answer: The pattern occurs 2 times.