Find minimum number of times to repeat string a so that b is a substring.
Input: a="abcd", b="cdabcdab" → Output: 3
Input: a="a", b="aa" → Output: 2
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
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)