Problem

Given two strings a and b, return the minimum number of times you should repeat stringa 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".

Examples

Example 1

1
2
3

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "ab**cdabcdab** cd", b is a substring of it.

Example 2

1
2

Input: a = "a", b = "aa"
Output: 2

Constraints

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

Solution

Method 1 - Greedy Repetition and Substring Check

Intuition

We want to repeat string a the minimum number of times so that b is a substring of the result. The minimum number of repeats is ceil(len(b)/len(a)), but we may need one or two more repeats to cover all cases.

Approach

  1. Compute the minimum number of repeats needed: repeats = ceil(len(b) / len(a)).
  2. Repeat a that many times and check if b is a substring.
  3. If not, try one more repeat, and if still not, try one more (at most two extra repeats are needed).
  4. If b is never a substring, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <string>
using namespace std;

int repeatedStringMatch(string a, string b) {
    string s = a;
    int count = 1;
    while (s.size() < b.size()) {
        s += a;
        count++;
    }
    if (s.find(b) != string::npos) return count;
    s += a;
    if (s.find(b) != string::npos) return count + 1;
    return -1;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import "strings"
func repeatedStringMatch(a, b string) int {
    s := a
    count := 1
    for len(s) < len(b) {
        s += a
        count++
    }
    if strings.Contains(s, b) {
        return count
    }
    s += a
    if strings.Contains(s, b) {
        return count + 1
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public class Solution {
    public int repeatedStringMatch(String a, String b) {
        StringBuilder sb = new StringBuilder(a);
        int count = 1;
        while (sb.length() < b.length()) {
            sb.append(a);
            count++;
        }
        if (sb.indexOf(b) != -1) return count;
        sb.append(a);
        if (sb.indexOf(b) != -1) return count + 1;
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

fun repeatedStringMatch(a: String, b: String): Int {
    val sb = StringBuilder(a)
    var count = 1
    while (sb.length < b.length) {
        sb.append(a)
        count++
    }
    if (sb.contains(b)) return count
    sb.append(a)
    if (sb.contains(b)) return count + 1
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def repeatedStringMatch(a: str, b: str) -> int:
    s = a
    count = 1
    while len(s) < len(b):
        s += a
        count += 1
    if b in s:
        return count
    s += a
    if b in s:
        return count + 1
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

fn repeated_string_match(a: &str, b: &str) -> i32 {
    let mut s = a.to_string();
    let mut count = 1;
    while s.len() < b.len() {
        s += a;
        count += 1;
    }
    if s.contains(b) {
        return count;
    }
    s += a;
    if s.contains(b) {
        return count + 1;
    }
    -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function repeatedStringMatch(a: string, b: string): number {
    let s = a;
    let count = 1;
    while (s.length < b.length) {
        s += a;
        count++;
    }
    if (s.includes(b)) return count;
    s += a;
    if (s.includes(b)) return count + 1;
    return -1;
}

Complexity

  • ⏰ Time complexity: O(N * M), where N = len(a), M = len(b) (for substring search).
  • 🧺 Space complexity: O(N + M), for the repeated string.