AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

String Matching coding problems

String matching asks where a pattern occurs inside a text.

14 problems · 6 easy · 3 medium · 5 hard · judged by hidden tests in 13 languages

14problems

6 easy

3 medium

5 hard

Sign in to tick off what you solve.

Study plan: 10 problems · about 5 h 50 min

Start the study plan

Next up: Rotate String

How it works

String Matching, step by step

Finding a pattern in a text, with naive string matching

text = "ababcabcab", pattern = "abc"

textpatterna0b1a2b3c4a5b6c7a8b9abcpositions to try: 0..7found: none yet

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.

0:01 / 0:29Step 1 of 10
Transcript · 10 steps

Study plan

Learn string matching in 6 days

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.

  1. Day 1

    about 1 h 15 min

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

  2. Day 2

    about 55 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 50 min

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

  5. Day 5

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  6. Day 6

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: KMP Algorithm

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

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

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.

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.

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 (6)

Medium (3)

Hard (5)

Companies that ask string matching problems

  • Amazon 10 problems on string matching
  • Google 10 problems on string matching
  • Microsoft 4 problems on string matching
  • Meta 1 problem on string matching
  • Myntra 1 problem on string matching

Next topic: KMP Algorithm