Is Repeated String Match easy or hard?

Repeated String Match is rated Medium difficulty. The implementation is simple, but recognizing that only two repetition checks are required requires careful reasoning about string alignment and substring boundaries.

Repeated String Match Python/Java solution

In Python or Java, the typical solution repeats string A until its length reaches or slightly exceeds B, then uses built-in substring search like `in` in Python or `contains()` in Java. The optimized approach checks only k and k+1 repetitions.

How to solve Repeated String Match in O(n)?

Compute the minimum number of repeats needed so the repeated string length is at least len(B). Build A repeated k times and check if B is a substring. If not found, append A once more and check again. These bounded checks keep the algorithm close to linear time.

What is the best approach for Repeated String Match?

The most efficient approach calculates the minimum repetitions needed using k = ceil(len(B) / len(A)), then checks whether B appears in A repeated k or k+1 times. This limits unnecessary string building and runs in roughly O(n + m) time using standard substring search.

Is Repeated String Match asked at Google/Amazon/Meta?

Repeated String Match is a common string manipulation problem frequently seen in technical interviews. Variants involving substring search and repeated patterns have appeared in interviews at companies like Amazon, Google, and Meta.

What data structure is used in Repeated String Match?

The problem primarily uses basic string operations and substring search. No complex data structures are required, but understanding string matching behavior and boundary overlaps between repetitions is key.

What is the time complexity of Repeated String Match?

The optimized solution runs in O(n + m) time where n is the length of A and m is the length of B. Only two substring checks are needed after computing the minimum repetition count. Space complexity is O(n) for the repeated string.

Description Solution Video 13:42

686. Repeated String Match

Medium39.7% acceptance6 companies

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.

Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".

Example 1:

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

Example 2:

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

Constraints:

1 <= a.length, b.length <= 10⁴
a and b consist of lowercase English letters.

Asked at 6 companies

Google Microsoft Uber Amazon Meta Bloomberg

Topics

String String Matching

13:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

686. Repeated String Match

Asked at 6 companies

Topics

Similar problems