Repeated String Match
Understanding the Problem
We need the smallest number of times to repeat string a so that b appears somewhere inside the repeated string. If b can never appear, we return -1.
Consider a = "abcd" and b = "cdab". Here b straddles a boundary between two copies of a: the cd comes from the end of one copy and the ab from the start of the next. We need at least 2 copies of a to cover the length of b, but in cases like this one we need one extra copy to span the overlap at the boundary.
That bounds the search. We never need more than ceil(len(b) / len(a)) + 1 repetitions. Once we have enough copies to cover the length of b plus one extra copy for boundary alignment, either b is already a substring or it never will be. The next section proves why one extra copy is always enough.
Key Constraints:
1 <= a.length, b.length <= 10^4. The repeated string we search reaches at mostm + 2n, roughly 30,000 characters, so building and scanning it directly is feasible.aandbconsist of lowercase English letters. This lets us use a 26-slot boolean array for a fast "does every character ofbappear ina" pre-check.
Approach 1: Build and Search
Intuition
Repeat a enough times to cover b, then ask the language whether b is a substring.
The bound from the previous section tells us exactly how many copies to build. With n = len(a) and m = len(b), we need at least minReps = ceil(m / n) copies to have enough characters, and at most one more to handle a match that starts partway through a copy. So only two candidates matter: minReps copies and minReps + 1 copies. Build the smaller one, search it, and if b is not found, append one more copy and search again.
One cheap pre-check rules out the impossible cases early. If b contains any character that does not appear in a, no number of repetitions can ever contain b, so we return -1 before building anything. Since both strings are lowercase letters, a 26-slot boolean array records which characters appear in a.
Algorithm
- Mark every character that appears in
a. If any character ofbis unmarked, return -1. - Compute
minReps = ceil(m / n). - Build
repeatedfromminRepscopies ofa. Ifbis a substring, returnminReps. - Append one more copy. If
bis now a substring, returnminReps + 1. - Otherwise return -1.
Example Walkthrough
Code
Why are minReps and minReps + 1 the only candidates worth checking?
If b is a substring of a repeated k times, that occurrence starts at some index s and the repeated string is periodic with period n = len(a). Shifting the occurrence left by n characters lands on the same pattern, so we can assume the match starts at an index s < n, that is, within the first copy. From there b spans s + m characters, which fits inside ceil((s + m) / n) copies. Since s < n, that value is at most ceil((n - 1 + m) / n) = ceil(m / n) + 1. So if b appears at all, it appears within minReps + 1 copies. Adding further copies only repeats alignments already covered.
Algorithm
- Mark every character that appears in
a. If any character ofbis unmarked, return -1. - Compute
minReps = ceil(m / n). - Build
repeatedfromminRepscopies ofa. Ifbis a substring, returnminReps. - Append one more copy. If
bis now a substring, returnminReps + 1. - Otherwise return -1.
Example Walkthrough
- Time Complexity: O(n m) worst case, O(n + m) typical. Building the repeated string takes O(n + m). The substring search depends on the language's implementation; most use linear-time algorithms in practice but can degrade to O(haystack needle) on adversarial inputs.
- Space Complexity: O(n + m). We store the repeated string, which has length at most m + 2n.
The repeated string here can be up to m + 2n characters, and the substring search has a quadratic worst case. The next approach removes both: it never builds the repeated string and matches in linear time.
Approach 2: Rabin-Karp (Rolling Hash)
Intuition
A rolling hash replaces character-by-character comparison at each alignment with a single integer comparison. Compute a hash of b, then slide a window of length m across the repeated a and compare the window's hash to the hash of b. When the hashes match, confirm with a direct character comparison, since two different strings can hash to the same value.
We do not build the repeated string. Position i of the virtual repeated string is a[i % n], so modular indexing reads any position on demand. That keeps space at O(1).
Rolling the hash forward by one position takes O(1) work: remove the contribution of the outgoing character, divide the hash by the base, and add the incoming character weighted by the highest power. Across all positions, the search runs in O(n + m) time.
Algorithm
- If any character of
bdoes not appear ina, return -1. - Set
minReps = ceil(m / n)and search overtotalLen = (minReps + 1) * ncharacters of the virtual repeated string. - Compute the polynomial rolling hash of
b. - Compute the hash of the first
m-character window of the virtual repeated string. - Slide the window one position at a time across every valid start. At each start:
- If the window hash equals the hash of
b, verify character by character using modular indexinga[(start + j) % n]. - If the characters match, return
ceil((start + m) / n), the number of copies the match spans. - Roll the hash forward by one position.
- If no start matches, return -1.
Example Walkthrough
Code
- Time Complexity: O(n + m). The hash of b takes O(m). Sliding across at most O(n) starting positions takes O(n) for the hash updates, with O(1) work per step. Collision verification adds O(m) per hash match but is rare with a well-chosen base and modulus.
- Space Complexity: O(1). A fixed number of hash values and counters, plus the 26-slot character array. No repeated string is built.
The two approaches trade off in opposite directions. Build and Search is short and relies on a fast built-in matcher, at the cost of O(m + 2n) memory and a quadratic worst case. Rabin-Karp guarantees O(n + m) time in O(1) space, at the cost of modular-arithmetic code that is harder to get right. For the constraints here (strings up to 10^4), Build and Search is the simpler choice; Rabin-Karp matters when the strings are large enough that building the concatenation is too costly.