Watch 10 video solutions for Repeated String Match, a medium level problem involving String, String Matching. This walkthrough by Aditya Verma has 19,998 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b to be a substring of a after repeating it, return -1.
Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".
Example 1:
Input: a = "abcd", b = "cdabcdab" Output: 3 Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.
Example 2:
Input: a = "a", b = "aa" Output: 2
Constraints:
1 <= a.length, b.length <= 104a and b consist of lowercase English letters.Problem Overview: You are given two strings A and B. The goal is to determine the minimum number of times A must be repeated so that B appears as a substring of the repeated result. If no amount of repetition makes this possible, return -1.
Approach 1: Repeating String Approach (O((n+m) * r) time, O(n * r) space)
This approach directly simulates the process described in the problem. Keep appending A to a growing string until its length becomes at least the length of B. After each repetition, check whether B appears as a substring using standard string search. If it does, return the current repetition count. If not, append A one more time to handle cases where B overlaps across the boundary of two repetitions.
The key insight is that a valid match must appear once the repeated string length reaches or slightly exceeds B. Since substring search itself scans characters sequentially, the total cost depends on both the lengths of the strings and the number of repetitions. This solution relies heavily on basic string operations and built-in substring search.
Approach 2: String Matching Optimization with Two Repeats (O(n + m) time, O(n) space)
This optimization reduces unnecessary repetitions by calculating the minimum base repeats needed before performing substring checks. Compute k = ceil(len(B) / len(A)), which guarantees that the repeated string is at least as long as B. Build the string by repeating A exactly k times and check if B is a substring.
If the match fails, append one more A and check again. At most two checks are required because any valid occurrence of B must either fit entirely inside the first k repetitions or overlap the boundary between repetitions. This keeps the search bounded and avoids building excessively large strings. The method combines reasoning about string lengths with efficient string matching behavior.
Recommended for interviews: The optimized repeat-count approach is what interviewers expect. It shows you understand how substring alignment works across repetition boundaries. Implementing the straightforward repeating approach first demonstrates problem understanding, while limiting the checks to k and k+1 repeats demonstrates algorithmic reasoning and awareness of edge cases.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeating String Approach | O((n+m) * r) | O(n * r) | Simple implementation when directly simulating repeated strings and substring checks. |
| String Matching Optimization with Two Repeats | O(n + m) | O(n) | Preferred interview solution. Limits repetition checks to k and k+1 using string length reasoning. |