Leetcode 686. Repeated String Match

Problem Explanation

You are given two strings A and B, your task is to find out the minimum number of times A has to be repeated such that B becomes a substring of the resulting string. If there are no such repetitions possible return -1.

A string s is said to be a substring of another string t if t contains s as a continuous sequence of characters.

Walk through an Example

For instance, consider A = "abcd" and B = "cdabcdab". Now, if A is repeated 3 times, it becomes abcdabcdabcd. If you observe closely, at the third repetition B becomes a substring of A. Thus, the answer will be 3 in this case.

Solution Approach

This solution uses the simple String matching algorithm.

Let's say n = len(B)/len(A). If B is a substring of A, it must be present when A is repeated n times or n+1 times because the length of B will not exceed the length of A repeated n+1 times.

Therefore, by iterating A over n times and conjoining A to s, check whether B is present in s. If it is, return n as the result. If it doesn't, join A to s once more, if B is then present in s, as a substring, the result is n + 1. If B is not a substring of s, return -1.

Python Solution

1
2python
3import math
4
5class Solution:
6    def repeatedStringMatch(self, A: str, B: str) -> int:
7        n = math.ceil(len(B) / len(A))
8        s = A * n
9
10        if B in s:
11            return n
12        if B in s + A:
13            return n + 1
14        return -1

Java Solution

1
2java
3public class Solution {
4    public int repeatedStringMatch(String A, String B) {
5        int n = (int) Math.ceil((double) B.length() / A.length());
6        String s = new String(new char[n]).replace("\0", A);
7
8        if (s.contains(B))
9            return n;
10        if ((s + A).contains(B))
11            return n + 1;
12        return -1;
13    }
14}

JavaScript Solution

1
2javascript
3class Solution {
4  repeatedStringMatch(A, B) {
5    const n = Math.ceil(B.length / A.length);
6    const s = A.repeat(n);
7
8    if (s.includes(B))
9      return n;
10    if ((s + A).includes(B))
11      return n + 1;
12    return -1;
13  }
14}

C++ Solution

1
2C++
3class Solution {
4public:
5    int repeatedStringMatch(string A, string B) {
6        const int n = ceil((double)B.size() / A.size());
7        string s;
8        
9        for(int i = 0; i < n; i++)
10            s += A;
11            
12        if (s.find(B) != string::npos)
13            return n;
14        if ((s + A).find(B) != string::npos)
15            return n + 1;
16        return -1;
17    }
18};

C# Solution

1
2C#
3public class Solution {
4    public int RepeatedStringMatch(string A, string B) {
5        int n = (int) Math.Ceiling((double) B.Length / A.Length);
6        string s = new String(A.ToCharArray()).Repeat(n);
7
8        if (s.Contains(B))
9            return n;
10        if ((s + A).Contains(B))
11            return n + 1;
12        return -1;
13    }
14}

Please note that for each language solution, all use the same principle in finding the minimum number of n where A has to be repeated such that B becomes a substring of the repeated A. The variance in solutions is only due to the syntax difference between these languages.## Complexity Analysis

Time Complexity

The time complexity for this problem is O(N) where N is the length of string A. We are performing the main operation (checking if B is a substring in S) only once or twice, which takes O(N) time. Additionally, string multiplication in Python also takes O(N) time and hence the overall complexity is linear.

Space Complexity

The space complexity is also O(N) where N is the length of string A. The string S is created by repeating string A multiple times, leading to a space complexity of O(N).

Conclusion

This kind of problem often encountered in DNA sequence alignment, spam detection, plagiarism detection, etc. It is used to find a shorter substring in a longer string. To tackle this problem, we should have a strong understanding of string manipulation in our programming language of choice. For our specific problem, the solutions use the same approach across different languages, with only minor adjustments for language-specific syntax.

The key to solving this problem is to understand the nature of substrings and why we only need to repeat A n times or n+1 times. Once that is clear, it's relatively straightforward to implement a solution in any programming language. However, keep in mind that the size of strings A and B could lead to a Time Limit Exceeded error in some cases if you use a straightforward method for checking if B is in A. Thus, these above solutions provide an efficient way to solve the problem.

Remember, practice is key to mastering any concept or language, so don't despair if you don't get it at first.