686. Repeated String Match
Repeated String Match (LeetCode 686) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the String Manipulation Patterns pattern, in the Naive / KMP / Rabin-Karp subpattern.
How to solve Repeated String Match
Repeated String Match is a String Matching problem, part of String Manipulation Patterns. Master string matching algorithms including naive search, KMP pattern matching, and Rabin-Karp hashing.
Work towards the solution in these steps:
- 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?
- 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.
- 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.
The reference solution runs in O((n + m) * n) time and O(n + m) space.
The Repeated String Match solution and editorial walks through the full approach with reference code.
Problem statement
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 <= 104
- a and b consist of lowercase English letters.
Topics and companies
Topics: String, String Matching.
Reported in interviews at Google, Facebook, Amazon.
How to practise Repeated String Match on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O((n + m) * n) time and O(n + m) space.
Open Repeated String Match in the code editor, or read the Repeated String Match editorial for a worked solution with its approach and complexity analysis.
Where Repeated String Match sits in the DSA pattern sheet
- String Manipulation Patterns pattern guide
- Naive / KMP / Rabin-Karp subpattern
- The full DSA patterns sheet
Problems related to Repeated String Match
Other problems that use the same Naive / KMP / Rabin-Karp and String Manipulation Patterns techniques:
- Find Beautiful Indices in the Given Array II — Hard, same subpattern
- Find the Index of the First Occurrence in a String — Easy, same subpattern
- Longest Common Prefix — Easy, same subpattern
- Rotate String — Easy, same subpattern
- Shortest Palindrome — Hard, same subpattern
- Add Strings — Easy, same pattern
Repeated String Match FAQ
What is the LeetCode number of Repeated String Match?
Repeated String Match is LeetCode problem 686, rated Medium.
What pattern is used to solve Repeated String Match?
Repeated String Match is a String Matching problem. It belongs to the String Manipulation Patterns pattern, in the Naive / KMP / Rabin-Karp subpattern.
What is the time complexity of Repeated String Match?
The reference solution runs in O((n + m) * n) time and O(n + m) space.
Which companies ask Repeated String Match?
Repeated String Match has been reported in interviews at Google, Facebook, Amazon.