Get started

String Matching Coding Problems: 3 Questions with Solutions

3 string matching coding problems — 2 easy · 1 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 2-day plan.

  • Problems: 3
  • By difficulty: 2 easy · 1 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

textmatch at 2match at 5a0b1a2b3c4a5b6c7a8b9matches at 2, 514 comparisons; worst case O(n × m)
Finding a pattern in a text, with naive string matching. Example: text = "ababcabcab", pattern = "abc"
  1. 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.
  2. 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.
  3. At s = 1 the very first comparison fails: 'b' is not 'a', so the pattern moves on after one look.
  4. At s = 2 all 3 characters agree: "abc" occurs at index 2. The search keeps going, to find every occurrence.
  5. 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.
  6. At s = 4, text[4] = 'c' fails against 'a' straight away — 9 comparisons so far.
  7. At s = 5 all 3 characters agree: "abc" occurs at index 5.
  8. At s = 6, text[6] = 'b' fails against 'a' straight away — 13 comparisons so far.
  9. At s = 7, text[7] = 'c' fails against 'a' straight away — 14 comparisons so far.
  10. "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

All 3 String Matching problems (2 easy and 1 hard) over 2 days, about 1 h 45 min in all — the pattern first, then easiest to hardest. Then move on to KMP Algorithm.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Next topic: KMP Algorithm

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] == pattern at every position: a hidden O(m) copy per step.

Start with

All string matching problems

Easy (2)

Hard (1)

Companies that ask string matching problems

  • Amazon 2 problems on string matching
  • Google 2 problems on string matching
  • Microsoft 2 problems on string matching

Next topic: KMP Algorithm