Repeated String Match

Repeated String Match

What is this problem about?

The Repeated String Match interview question asks you to find the minimum number of times you must repeat string a so that string b is a substring of the repeated version of a. If no such repetition count makes b a substring of the repeated a, return -1. This is a string matching problem that combines repeated string construction with substring search.

Why is this asked in interviews?

This problem is asked at Uber, Microsoft, Meta, Amazon, and Google because it tests understanding of string repetition bounds and substring search. The key insight is that you only need to repeat a at most ceil(len(b) / len(a)) + 1 times — beyond that, if b hasn't appeared, it never will. It also sets the stage for discussing advanced string matching algorithms like KMP or Rabin-Karp for follow-ups.

Algorithmic pattern used

The pattern is repeated string construction with boundary analysis. The minimum repetitions needed is ceil(len(b) / len(a)). Try repeating a that many times and check if b is a substring. If not, try one more repetition. If still not found, return -1. The reasoning: b must start within the first len(a) characters of some repetition of a, and once started, it spans at most ceil(len(b)/len(a)) + 1 copies.

Example explanation

a = "abc", b = "cabcabc".

len(b)=7, len(a)=3. Minimum repetitions = ceil(7/3) = 3.

Repeated 3 times: "abcabcabc". Does it contain "cabcabc"? Check: "abcabcabc" — yes, starting at index 2! Return 3.

a = "abc", b = "abcd".

Repeated 2 times: "abcabc". Contains "abcd"? No. Repeated 3 times: "abcabcabc". Contains "abcd"? No. Return -1.

Common mistakes candidates make

• Repeating a too many times in a loop without the mathematical upper bound, leading to TLE.
• Forgetting the "+1" extra repetition check — b might span the boundary into one extra copy.
• Using in operator without understanding its O(n*m) cost — for very large strings, KMP or Rabin-Karp is preferable.
• Returning the wrong count when b is found on the second repetition attempt (off-by-one in the repetition count).

Interview preparation tip

For the Repeated String Match coding problem, the string matching interview pattern is clean once you know the upper bound: try ceil(len(b)/len(a)) and ceil(len(b)/len(a)) + 1 repetitions only. Interviewers at Meta and Google sometimes ask for a KMP-based O(n+m) solution as a follow-up — knowing the boundary analysis is the same regardless of the matching algorithm. Practice articulating why at most two repetition counts need to be tested to show mathematical confidence.