Repeated String Match

Med

#0640Time: O((m + n) * m), where `m` is the length of `b` and `n` is the length of `a`. The `StringBuilder` construction takes O(m+n). The `contains()` method, in the worst case, takes O(text_length * pattern_length). The text length is O(m+n) and the pattern length is `m`.Space: O(m + n), where `m` is the length of `b` and `n` is the length of `a`. This is for the `StringBuilder`, which grows to a length of approximately `m+n`.

Patterns

String Matching

Data structures

String

Prompt

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 <= 10⁴
a and b consist of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We start with string a and keep appending copies of a to it until the resulting string is long enough to potentially contain b. The key is to realize that we don't need to loop indefinitely. If b is a substring of a repeated a, it must be found within a string formed by repeating a just enough times for its length to be at least b.length(), or that same string with one more a appended to handle cases where b wraps around the concatenation point.

Algorithm

Initialize a StringBuilder sb with the string a and a counter count to 1.
In a loop, continue appending a to sb and incrementing count until the length of sb is greater than or equal to the length of b.
After the loop, let's say count is k. The string sb is a repeated k times. Check if b is a substring of sb using String.contains().
If it is, k is the minimum number of repetitions, so return count.
If not, the match might span across the boundary into the next repetition of a. Append a one more time to sb.
Check if b is a substring of the new, longer sb.
If it is, the answer is count + 1.
If it's still not a substring, it's impossible to form b. Return -1.

Walkthrough

We use a StringBuilder for efficient string concatenation. We first build a string S by repeating a until S's length is at least b's length. Let's say this takes k repetitions. We then check if b is a substring of S. If it is, we've found our answer: k. If not, there's one more possibility: b could be a substring that starts near the end of S and finishes in the next block of a. For example, if a = "abcd" and b = "cdab", b is not in "abcd", but it is in "abcdabcd". So, we perform one final check: we append a to S one more time and check again. If b is a substring now, the answer is k + 1. If not, it can never be a substring, so we return -1.

1class Solution {2    public int repeatedStringMatch(String a, String b) {3        StringBuilder sb = new StringBuilder();4        int count = 0;5        while (sb.length() < b.length()) {6            sb.append(a);7            count++;8        }9        10        // Check if b is in the current repeated string11        if (sb.toString().contains(b)) {12            return count;13        }14        15        // Append a one more time to handle wrap-around cases16        sb.append(a);17        if (sb.toString().contains(b)) {18            return count + 1;19        }20        21        return -1;22    }23}

Complexity

Time

O((m + n) * m), where `m` is the length of `b` and `n` is the length of `a`. The `StringBuilder` construction takes O(m+n). The `contains()` method, in the worst case, takes O(text_length * pattern_length). The text length is O(m+n) and the pattern length is `m`.

Space

O(m + n), where `m` is the length of `b` and `n` is the length of `a`. This is for the `StringBuilder`, which grows to a length of approximately `m+n`.

Trade-offs

Pros

The logic is straightforward and easy to implement.
It correctly handles all cases, including the wrap-around case.

Cons

The worst-case time complexity is high due to the substring search (String.contains()) on a potentially long string. If the underlying implementation is a naive character-by-character comparison, this can lead to a Time Limit Exceeded error on large inputs.

This approach optimizes the previous one by replacing the potentially slow substring search with a guaranteed linear-time algorithm. Algorithms like Rabin-Karp (using a rolling hash) or Knuth-Morris-Pratt (KMP) can find a pattern in a text in time proportional to the sum of their lengths, a significant improvement over the naive quadratic approach. While Java's built-in String.indexOf() (used by contains()) is highly optimized (often using algorithms like Boyer-Moore), relying on a custom implementation of KMP or Rabin-Karp provides a theoretical guarantee of performance.

Algorithm

The overall structure is the same as the simple iterative approach. We build a text string S by repeating a.
Instead of using String.contains(), we use a more efficient string searching algorithm like Rabin-Karp or Knuth-Morris-Pratt (KMP).
Rabin-Karp Logic:
1. Calculate the hash of the pattern string b.
2. Build the text string S by repeating a until S.length() >= b.length(). Let this take k repetitions.
3. Use a rolling hash to efficiently calculate the hash of every substring of S that has the same length as b.
4. If a substring's hash matches b's hash, perform a direct character comparison to confirm the match (to avoid hash collisions).
5. If a match is found in S, return k.
6. If no match is found, append a to S and search again in the newly formed string.
7. If a match is found now, return k+1. Otherwise, return -1.

Walkthrough

The strategy is to reduce the time complexity of the search step. We still construct the candidate string S by repeating a until its length is at least b's length, and then check S and S + a. However, the check S.contains(b) is replaced by a call to a more efficient search function.

A Rabin-Karp implementation would involve choosing a prime modulus and a base for the hash function. It would compute the hash of b and then slide a window of length b.length() over S, updating the hash in O(1) time at each step. This makes the search operation much faster.

For practical purposes, using the built-in String.indexOf() in Java is often sufficient as it is heavily optimized. The code would look identical to the first approach, but the justification for its efficiency would rely on the performance of the underlying library implementation rather than a naive search assumption. This approach is about recognizing that the bottleneck is the search and that linear-time solutions exist for it.

1class Solution {2    // The code is identical to the simple approach, but we analyze its3    // complexity assuming the underlying .contains()/.indexOf() is optimized4    // to run in linear time, like Rabin-Karp or Boyer-Moore.5    public int repeatedStringMatch(String a, String b) {6        StringBuilder sb = new StringBuilder();7        int count = 0;8        while (sb.length() < b.length()) {9            sb.append(a);10            count++;11        }12        13        if (sb.toString().indexOf(b) != -1) {14            return count;15        }16        17        sb.append(a);18        if (sb.toString().indexOf(b) != -1) {19            return count + 1;20        }21        22        return -1;23    }24}

Complexity

Time

O(m + n), where `m` is the length of `b` and `n` is the length of `a`. Building the string takes O(m+n). An efficient search algorithm like Rabin-Karp or KMP takes O(text_length + pattern_length) = O((m+n) + m) = O(m+n).

Space

O(m + n), for the `StringBuilder` which stores the repeated string.

Trade-offs

Pros

Provides a guaranteed optimal time complexity.
It is very efficient and will pass for all input constraints.

Cons

Implementing advanced algorithms like Rabin-Karp or KMP from scratch is more complex and error-prone than using built-in functions.

Solutions

Solution

1class Solution { public int repeatedStringMatch ( String a , String b ) { int m = a . length (), n = b . length (); int ans = ( n + m - 1 ) / m ; StringBuilder t = new StringBuilder ( a . repeat ( ans )); for ( int i = 0 ; i < 3 ; ++ i ) { if ( t . toString (). contains ( b )) { return ans ; } ++ ans ; t . append ( a ); } return - 1 ; } }

1class Solution { public: int repeatedStringMatch ( string a , string b ) { int m = a . size (), n = b . size (); int ans = ( n + m - 1 ) / m ; string t = "" ; for ( int i = 0 ; i < ans ; ++ i ) t += a ; for ( int i = 0 ; i < 3 ; ++ i ) { if ( t . find ( b ) != - 1 ) return ans ; ++ ans ; t += a ; } return - 1 ; } };

1class Solution : def repeatedStringMatch ( self , a : str , b : str ) -> int : m , n = len ( a ), len ( b ) ans = ceil ( n / m ) t = [ a ] * ans for _ in range ( 3 ): if b in '' . join ( t ): return ans ans += 1 t . append ( a ) return - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem