Repeated String Match — Ceiling Division String Matching [LC 686]

Problem Statement#

Given two strings a and b, return the minimum number of times you should repeat string a such that string b is a substring of the repeated a. If it is not possible, return -1.

Constraints:

• 1 <= a.length, b.length <= 10^4
• a and b consist of lowercase English letters

Input:  a = "abcd", b = "cdabcdab"
Output: 3

Input:  a = "a", b = "aa"
Output: 2

Why This Problem Matters#

LeetCode 686 is a Google and Amazon interview problem that tests clean mathematical reasoning about string repetition. The key insight — you only ever need to check ceil(len(b)/len(a)) or ceil(len(b)/len(a)) + 1 repetitions — reduces an unbounded search to at most two substring checks.

The problem also appears as a sub-problem in DNA sequence analysis and circular string matching. The ceiling division trick is a clean example of using math to bound what initially looks like an unbounded loop.

The Core Insight#

Minimum repetitions needed: If b is a substring of repeated(a), the repeated string must be at least len(b) characters long. The minimum length of repeated(a) that could contain b is ceil(len(b) / len(a)) repetitions.

However, b might start near the end of one copy and end in a subsequent copy. So we might need one extra repetition. Therefore: check ceil(len(b)/len(a)) repetitions, then check ceil(len(b)/len(a)) + 1. If b isn't found in either, return -1.

We never need more than ceil(len(b)/len(a)) + 1 because any extra repetitions beyond that would be padding beyond what b's length could require.

Visual Dry Run#

a = "abcd", b = "cdabcdab"

len(b) = 8, len(a) = 4 min_reps = ceil(8/4) = 2

Check a * 2 = "abcdabcd" — does "cdabcdab" appear? "abcdabcd" — no. Check a * 3 = "abcdabcdabcd" — does "cdabcdab" appear? "abcdabcdabcd" — YES at position 2!

Return 3.

Solution (Optimal)#

import math
 
class Solution:
    def repeatedStringMatch(self, a, b):
        reps = math.ceil(len(b) / len(a))
        repeated = a * reps
        if b in repeated:
            return reps
        repeated += a
        if b in repeated:
            return reps + 1
        return -1

var repeatedStringMatch = function(a, b) {
    const reps = Math.ceil(b.length / a.length);
    let repeated = a.repeat(reps);
    if (repeated.includes(b)) return reps;
    repeated += a;
    if (repeated.includes(b)) return reps + 1;
    return -1;
};

Time: O(n * m) — substring check via built-in string matching, where n = len(a)*reps and m = len(b) Space: O(n + m) — the repeated string

Common Mistakes#

• Looping and incrementing reps one by one until found — O(m/n) iterations each with O(n*m) substring check, unnecessarily slow
• Not checking reps + 1 — b might span across a boundary and need one extra copy
• Checking more than reps + 1 — never needed, returning -1 after two checks is correct
• Using // (floor division) instead of ceil — floor may start one repetition too short
• Off-by-one: using len(b) // len(a) directly without ceiling — "cdabcdab" in "abcd"*2 would miss the boundary case

Interview Tips#

• State the key bound: "we need at least ceil(len(b)/len(a)) copies, possibly one more if b straddles a boundary"
• Explain why not more than one extra: "any substring of repeated(a) spanning more than ceil+1 copies would be longer than len(b)"
• Trace through the example: show a*2 failing and a*3 succeeding
• Mention KMP as the theoretical O(n+m) string matching — but the built-in in operator is fine for this problem size
• Compare with Rotate String (LC 796) — both use the "build a longer string, then do substring check" pattern

Follow-up Questions#

• How can you implement the substring check in O(n+m) instead of O(n*m)? (KMP algorithm or Rabin-Karp rolling hash)
• What if a can be repeated an unlimited number of times — what's the maximum repetitions before we know it's impossible? (ceil(len(b)/len(a)) + 1 — anything beyond this is definitively impossible)
• How does this relate to Rotate String (LC 796)? (Both: construct a longer composed string, check for substring — same paradigm)
• What if b contains characters not in a? (Return -1 immediately — substring check will naturally fail, but early exit saves time)
• What if a itself contains b? (1 repetition is enough — reps = ceil(len(b)/len(a)) would be 0 rounded up to 1, handled correctly)

Key Takeaways#

• LeetCode 686 is asked at Google and Amazon — ceiling division bounds the repetitions to check
• Minimum check: reps = ceil(len(b)/len(a)) — the smallest number of copies where b could fit
• Always check reps and reps + 1 — b might straddle a copy boundary, requiring one extra
• Never need more than reps + 1 — mathematically provable from the length constraint
• Time O(n*m) for substring check using built-in; O(n+m) with KMP
• Characters-not-in-a is an optional early exit: if b contains any character not in a, return -1 immediately
• The "repeat to fit, then check" pattern also solves Rotate String and periodic string matching problems