Problem statement

Given two strings a and b, return the minimum number of times a must be repeated (written end to end) so that b becomes a substring of the result. If no number of repetitions works, return -1.

Repeating "abc" zero times gives "", once gives "abc", twice gives "abcabc".

Example 1

Input: a = "kai", b = "aikaik"
Output: 3
Explanation: `"kaikaikai"` contains `"aikaik"` starting at index 1; `"kaikai"` is too short to.

Example 2

Input: a = "z", b = "zzzz"
Output: 4

Example 3

Input: a = "abc", b = "acb"
Output: -1
Explanation: In any repetition of `a`, the letter after `a` is always `b`.

Constraints

• 1 <= a.length, b.length <= 10^4
• a and b consist of lowercase English letters

Hints for Repeated String Match

1. Hint 1

   The repeated string must at least be as long as b, so you need at least q = ceil(|b| / |a|) copies.

2. Hint 2

   If b occurs at all, it starts inside the first copy of a. Starting there, it ends within q + 1 copies.

3. Hint 3

   So only two candidates matter: check a repeated q times, then q + 1 times; otherwise answer -1.

How to solve Repeated String Match

Any occurrence of b in a long repetition of a can be shifted left by whole copies until it starts in the first copy, and from there it spans at most q + 1 copies, where q = ceil(|b| / |a|).

Approach

1. Build s by appending a until |s| >= |b|; let q be the number of copies used.
2. If b is a substring of s, return q.
3. Append one more a; if b is now a substring, return q + 1.
4. Otherwise return -1.

Why it works

Fewer than q copies are shorter than b, so q is a lower bound. If b occurs in some repetition, shift the occurrence left by multiples of |a| (the string is periodic) until it starts at an offset o < |a|; it then ends before o + |b| < |a| + q·|a|, inside q + 1 copies. Hence if neither candidate contains b, no repetition does.

Complexity

• Time — O(|a| + |b|) with a linear-time matcher (KMP / Z); a library substring search is fine in practice
• Space — O(|a| + |b|)

Pitfalls

• Checking only q copies misses cases like a = "abcd", b = "cdab", which need one extra copy.
• Looping on more and more copies without a bound never terminates when the answer is -1.

Reference solution

Python

def repeatedStringMatch(a: str, b: str) -> int:
    q = -(-len(b) // len(a))  # ceil
    s = a * q
    if b in s:
        return q
    if b in s + a:
        return q + 1
    return -1

Java

public static int repeatedStringMatch(String a, String b) {
    int q = (b.length() + a.length() - 1) / a.length();
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < q; i++) sb.append(a);
    if (sb.indexOf(b) != -1) return q;
    sb.append(a);
    if (sb.indexOf(b) != -1) return q + 1;
    return -1;
}

C++

int repeatedStringMatch(string a, string b) {
    int q = ((int) b.size() + (int) a.size() - 1) / (int) a.size();
    string s;
    for (int i = 0; i < q; i++) s += a;
    if (s.find(b) != string::npos) return q;
    s += a;
    if (s.find(b) != string::npos) return q + 1;
    return -1;
}

JavaScript

var repeatedStringMatch = function(a, b) {
    var q = Math.ceil(b.length / a.length);
    var s = "";
    for (var i = 0; i < q; i++) s += a;
    if (s.indexOf(b) !== -1) return q;
    if ((s + a).indexOf(b) !== -1) return q + 1;
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium