686. Repeated String Match LeetCode Solution

In this guide, you will get 686. Repeated String Match LeetCode Solution with the best time and space complexity. The solution to Repeated String Match problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Repeated String Match solution in C++
4. Repeated String Match solution in Java
5. Repeated String Match solution in Python
6. Additional Resources

Problem Statement of Repeated String Match

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.

Complexity Analysis

• Time Complexity: O(|\texttt{a}| + |\texttt{b}|)
• Space Complexity: O(|\texttt{a}| + |\texttt{b}|)

686. Repeated String Match LeetCode Solution in C++

class Solution {
 public:
  int repeatedStringMatch(string a, string b) {
    const int n = ceil((double)b.length() / a.length());
    string s;

    for (int i = 0; i < n; ++i)
      s += a;

    if (s.find(b) != string::npos)
      return n;
    if ((s + a).find(b) != string::npos)
      return n + 1;
    return -1;
  }
};
/* code provided by PROGIEZ */

686. Repeated String Match LeetCode Solution in Java

class Solution {
  public int repeatedStringMatch(String A, String B) {
    final int n = (int) Math.ceil((double) B.length() / (double) A.length());
    final String s = String.join("", Collections.nCopies(n, A));
    if (s.contains(B))
      return n;
    if ((s + A).contains(B))
      return n + 1;
    return -1;
  }
}
// code provided by PROGIEZ

686. Repeated String Match LeetCode Solution in Python

class Solution:
  def repeatedStringMatch(self, a: str, b: str) -> int:
    n = math.ceil(len(b) / len(a))
    s = a * n
    if b in s:
      return n
    if b in s + a:
      return n + 1
    return -1
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.