Last updated on March 1st, 2025 at 07:26 pm

Here, we see a Repeated String Match LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Bit Manipulation, Hash Table

Companies

Level of Question

Medium

Repeated String Match LeetCode Solution

1. 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

2. Coding Pattern Used in Solution

The coding pattern used in this problem is “String Manipulation with Repeated Concatenation”. The goal is to determine the minimum number of times string a needs to be repeated such that string b becomes a substring of the repeated string.

3. Code Implementation in Different Languages

3.1 Repeated String Match C++

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        string s="";
        int count = 0;
        while(s.size()<b.size())
        {
            s+=a;
            count++;
        }
        if(s.find(b)!=string::npos)
            return count;
        s+=a;
        count++;
        if(s.find(b)!=string::npos)
            return count;
        return -1;
    }
};

3.2 Repeated String Match Java

class Solution {
    public int repeatedStringMatch(String a, String b) {
    StringBuilder gy=new StringBuilder();
        int I=0;
    for(I=1; gy.length()&lt;=b.length(); I++){
        gy.append(a);
        if(gy.toString().contains(b))return I;
    }
        if(gy.append(a).toString().contains(b))return I;
        return -1;
    }
}

3.3 Repeated String Match JavaScript

var repeatedStringMatch = function(a, b) {
    const count = Math.ceil(b.length / a.length)
    const str = a.repeat(count)
    return str.includes(b) ? count : (str + a).includes(b) ? count + 1 : -1     
};

3.4 Repeated String Match Python

class Solution(object):
    def repeatedStringMatch(self, a, b):
    	if set(b).issubset(set(a)) == False: return -1
    	for i in range(1,int(len(b)/len(a))+3):
    		if b in a*i: return i
    	return -1

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n * m)	O(n + m)
Java	O(n * m)	O(n + m)
JavaScript	O(n * m)	O(n + m)
Python	O(n * m)	O(n + m)

Time Complexity: The dominant operation is the substring search (find, contains, includes, or in), which is O(n * m) in the worst case. This is because for each repetition of a, the algorithm checks if b is a substring.
Space Complexity: The space complexity is O(n + m) because the repeated string can grow up to the size of b plus one additional repetition of a.