#686
Repeated String Match
Medium Repeat + KMP search
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the fewest times you must repeat string a so that b becomes a substring of the result, or -1 if it's impossible.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the fewest copies of a so that b fits inside.
Why this works: you need at least enough copies to be as long as b; one extra copy covers b starting in the middle of a copy.
Example: a = "abcd", b = "cdabcdab"
2 copies "abcdabcd" — not inside3 copies "abcdabcdabcd" — contains b → 3
✦Hints open one at a time
You need at least ceil(|b| / |a|) copies to be long enough.
One more copy covers every possible starting offset. If b isn't found with that many, it never will be.
↗Approach
Repeat a until its length is at least |b|, check for b; if not found, add one more copy and check again. Use KMP (or indexOf) for the check.
</>Solution (Java)
class Solution {
public int repeatedStringMatch(String a, String b) {
StringBuilder sb = new StringBuilder();
int count = 0;
while (sb.length() < b.length()) {
sb.append(a);
count++;
}
if (indexOf(sb.toString(), b) >= 0) return count;
if (indexOf(sb.append(a).toString(), b) >= 0) return count + 1; // one extra for the offset
return -1;
}
// KMP search
private int indexOf(String text, String pat) {
int m = pat.length();
int[] lps = new int[m];
for (int i = 1, len = 0; i < m; ) {
if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
for (int i = 0, j = 0; i < text.length(); ) {
if (text.charAt(i) == pat.charAt(j)) {
i++;
if (++j == m) return i - m;
} else if (j > 0) j = lps[j - 1];
else i++;
}
return -1;
}
}!Common mistake
Stopping at ceil(|b| / |a|) copies — b may start in the middle of a copy and need one extra.
Complexity
- Time: O(n + m) with KMP.
- Space: O(n + m).
Topic: String Pattern Matching
🎬 Episodes 18–19: video coming soon