String Matching Coding Problems: 14 Questions with Solutions
14 string matching coding problems — 6 easy · 3 medium · 5 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 6-day plan.
- Problems: 14
- By difficulty: 6 easy · 3 medium · 5 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
String matching asks where a pattern occurs inside a text. Trying every start position letter by letter costs the text's length times the pattern's; the classic algorithms — Knuth–Morris–Pratt, the Z-function, Rabin–Karp — bring that down to linear time by never comparing the same text character twice, or by comparing hashes instead of letters. The problems here practise those searches and the reductions that turn other questions into one: a rotation of a string is a substring of the string written twice.
How string matching works, step by step
text = "ababcabcab", pattern = "abc"- Naive search tries the pattern "abc" at every starting position s of the text, comparing left to right and giving up at the first mismatch. A text of 10 and a pattern of 3 leave 10 − 3 + 1 = 8 positions to try.
- At s = 0, "ab" matches but text[2] = 'a' is not 'c'. The 2 matched characters are thrown away and the pattern shifts by just one place, so they will be read again.
- At s = 1 the very first comparison fails: 'b' is not 'a', so the pattern moves on after one look.
- At s = 2 all 3 characters agree: "abc" occurs at index 2. The search keeps going, to find every occurrence.
- At s = 3, 'b' is not 'a' either: one comparison and the pattern shifts again. A mismatch on the first character is the cheap case.
- At s = 4, text[4] = 'c' fails against 'a' straight away — 9 comparisons so far.
- At s = 5 all 3 characters agree: "abc" occurs at index 5.
- At s = 6, text[6] = 'b' fails against 'a' straight away — 13 comparisons so far.
- At s = 7, text[7] = 'c' fails against 'a' straight away — 14 comparisons so far.
- "abc" occurs at 2 and 5. All 8 positions were tried with 14 character comparisons; in the worst case each costs m, so naive search is O(n × m) — and it re-reads text it has already matched.
String Matching study plan
10 of the 14 String Matching problems (4 easy, 3 medium and 3 hard) over 6 days, about 5 h 50 min in all — the pattern first, then easiest to hardest. After that, the other 4 in the full list below are practice at your own pace. Then move on to KMP Algorithm.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Minimum Time to Revert Word to Initial State I Medium
- Number of Subarrays That Match a Pattern I Medium
Day 4
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 5
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 6
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
String Matching: the essentials
When to reach for it
"Find every occurrence", "is goal a rotation of s", "is s made of copies of one block". Checking each start position letter by letter is O(n × m): fine for short strings, too slow when the text runs to 10⁵ and the pattern is long or mostly one letter.
The pattern
Reduce first. goal is a rotation of s exactly when the lengths match and goal occurs in s + s; s repeats a shorter block exactly when it occurs in s + s without its first and last characters. Then search in linear time. The Z-function gives each position's longest match with the string's start; over pattern + text, a text position whose value reaches the pattern's length starts a match. KMP builds a border table instead.
def find_all(text, pattern): # every start index, overlaps included
s, m = pattern + text, len(pattern)
n = len(s)
z, l, r = [0] * n, 0, 0 # z[i]: common prefix of s and s[i:]
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return [i - m for i in range(m, n) if z[i] >= m]
Cost
The Z-function and KMP take O(n + m) time and space, Rabin–Karp the same on average. A library search is not guaranteed linear: Java's indexOf is naive, O(n × m) at worst.
Common mistakes
- Missing overlapping matches by resuming at i + m after a match at i, not i + 1.
- Skipping the length check in the rotation test: "ab" occurs in "abcabc" but is not a rotation of "abc".
- Joining pattern and text with a separator that can occur in the input, so a match spans the join.
- Comparing
text[i:i + m] == patternat every position: a hidden O(m) copy per step.
Start with
- Rotate String: a rotation is a substring of
s + s. - Repeated Substring Pattern:
sinsides + swith its ends trimmed. - String Matching: All Occurrences: every overlapping match in linear time.
All string matching problems
Easy (6)
- Subtree of Another Tree Tree, Depth-First Search
- Substring Matching Pattern String
- Counting Words With a Given Prefix Array, String
- String Matching in an Array Array, String
- Rotate String String
- Repeated Substring Pattern String
Medium (3)
- Number of Subarrays That Match a Pattern I Array, Rolling Hash
- Minimum Time to Revert Word to Initial State I String, Rolling Hash
- Repeated String Match String, Rolling Hash
Hard (5)
- Number of Subarrays That Match a Pattern II Array, Rolling Hash
- Minimum Time to Revert Word to Initial State II String, Rolling Hash
- Maximum Deletions on a String String, Dynamic Programming, Rolling Hash
- Sum of Scores of Built Strings String, Rolling Hash, Binary Search
- String Matching: All Occurrences String, Rolling Hash
Companies that ask string matching problems
Next topic: KMP Algorithm