Repeated String Match

MEDIUM

Description

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

Checkout 2 different approaches to solve Repeated String Match. Click on different approaches to view the approach and algorithm in detail.

Simple Iteration with String Matching

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.

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 Analysis

Time Complexity: 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 Complexity: 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`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Repeated String Match. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Repeated String Match

Patterns:

String Matching

Data Structures:

String