Repeated String Match
Problem
a and b, find the fewest number of times
a must be written back-to-back so that b appears inside the result as a
contiguous substring. Return -1 if no number of copies works. (Zero copies is the
empty string.)a = "abcd", b = "cdabcdab"Output3 (abcdabcdabcd)a = "a", b = "aa"Output2a = "abc", b = "wxyz"Output-11 ≤ a.length, b.length ≤ 104 · lowercase English letters
Try it yourself
class Solution {
public int repeatedStringMatch(String a, String b) {
}
}
b occurs at all, it starts within the first copy of
a (offset < n). So scanning a text of length n + m is enough, and
KMP can walk that text virtually using a.charAt(i % n).Instinct Find a pattern in a text, or a prefix that is also a suffix, faster than O(n·m) - reach for the KMP prefix function or a rolling hash.
Memory hack KMP remembers borders, Rabin-Karp compares fingerprints - neither one re-reads text it has already seen.
Open the String Matching guide →Approaches
Brute ForceAppend and Search Each Time
O((m/n + 2) · (n+m) · m)Space O(n + m)Keep appending a and search for b after every append.
Once the built string is at least n + m long without a match, give up: any
match must start at an offset < n, so it would already fit.
public int repeatedStringMatch(String a, String b) { StringBuilder sb = new StringBuilder(); int copies = 0; while (sb.length() < a.length() + b.length()) { sb.append(a); copies++; if (sb.indexOf(b) >= 0) return copies; } return -1; }
Correct and simple, but repeats a full substring search after every copy.
BetterBuild Once, Search Once
O((n+m) · m)Space O(n + m)Build q + 1 copies where q = ceil(m / n); that text has
length ≥ n + m, so it contains b iff any repetition does.
One indexOf gives the first start s; the copies needed are
ceil((s + m) / n).
public int repeatedStringMatch(String a, String b) { int n = a.length(), m = b.length(); int q = (m + n - 1) / n; String text = a.repeat(q + 1); int s = text.indexOf(b); if (s < 0) return -1; return (s + m + n - 1) / n; // copies covering text[0 .. s+m-1] }
Single search, but naive indexOf is still O((n+m)·m) in the worst case.
OptimalKMP over a Virtual Repeated Text
O(n + m)Space O(m)Build the KMP failure table of b, then stream the text
a[i % n] for i = 0 .. n+m-1 without materialising it. The first
full match ends at index i, which lies in copy number
i / n + 1 — that is the answer.
public int repeatedStringMatch(String a, String b) { int n = a.length(), m = b.length(); int[] fail = new int[m]; // longest proper border of b[0..i] for (int i = 1, k = 0; i < m; i++) { while (k > 0 && b.charAt(i) != b.charAt(k)) k = fail[k - 1]; if (b.charAt(i) == b.charAt(k)) k++; fail[i] = k; } for (int i = 0, j = 0; i < n + m; i++) { char c = a.charAt(i % n); while (j > 0 && c != b.charAt(j)) j = fail[j - 1]; if (c == b.charAt(j)) j++; if (j == m) return i / n + 1; // match ends inside copy i / n } return -1; }
Dry runa = "abcd", b = "cdabcdab"
- textabcabcabca=abc, b=cab
- i=2abciabcabcc matches, j=1
- i=3abcaibcabcj=2
- i=4abcabicabcj=3=m → 4/3+1 = 2 ✔
Linear time, O(m) memory, and no repeated string is ever built.
b uses a letter missing from a, return
-1 immediately.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Append and Search Each Time | O((m/n + 2) · (n+m) · m) | O(n + m) |
| Better | Build Once, Search Once | O((n+m) · m) | O(n + m) |
| Optimal | KMP over a Virtual Repeated Text | O(n + m) | O(m) |
- Stopping at
ceil(m/n)copies — an offset start may need one more copy. - Looping forever when there is no match — bound the text length by
n + m. - Off-by-one in
ceil: use(x + n - 1) / nwith integers.
- State the bound first: the match must begin inside the first copy of
a. - Offer the build-and-indexOf version, then upgrade to KMP (or Rabin–Karp) for linear time.
- Point out the modulo trick avoids allocating the repeated string.