Scale Engineer

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 <= 104
  • 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.

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++;        }                // Check if b is in the current repeated string        if (sb.toString().contains(b)) {            return count;        }                // Append a one more time to handle wrap-around cases        sb.append(a);        if (sb.toString().contains(b)) {            return count + 1;        }                return -1;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem