686. Repeated String Match

How to solve Repeated String Match (LeetCode 686): the approach in brief

The problem

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.

Pattern

Repeated String Match is a String Manipulation Patterns problem, in the Naive / KMP / Rabin-Karp subpattern. The pattern covers palindrome checking, anagram detection, pattern matching, and string conversion

Master string matching algorithms including naive search, KMP pattern matching, and Rabin-Karp hashing.

Approach outline

1. Consider how repeating string 'a' multiple times can create a longer string in which 'b' might be a substring; what is the minimum length needed for this repeated string?
2. Think about the relationship between the lengths of 'a' and 'b' to estimate the minimum number of repetitions of 'a' required to contain 'b' as a substring.
3. Once you have an idea of how many times to repeat 'a', consider checking if 'b' is a substring within the repeated string using built-in substring search methods or efficient string matching algorithms like KMP.

Complexity

The reference solution runs in O((n + m) * n) time and O(n + m) space.

Asked at

Repeated String Match has been reported in interviews at Google, Facebook, Amazon.