Repeated String Match

Share

Find minimum number of times to repeat string a so that b is a substring.

Example 1
Input: a="abcd", b="cdabcdab" → Output: 3
Example 2
Input: a="a", b="aa" → Output: 2

Solution Approach

Repeat a until length >= b.length. Check for b. Try one more repetition.

  • Repeat a until its length >= b.length (call it rep)
  • Check if b is substring of rep
  • If not, try rep + a (one extra)
  • Return count or -1
Java
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);
    return sb.indexOf(b) != -1 ? count + 1 : -1;
}
  • Time Complexity: O(n+m)
  • Space Complexity: O(n+m)