686. Repeated String Match

MediumStringString Matching
Leetcode Link

Problem Description

The task is to determine how many times we need to repeat string a such that string b becomes a substring of the repeated string a.

Here are important things to note from the problem:

  • If it is not possible for b to be a substring of a no matter how many times a is repeated, we should return -1.
  • A string repeated 0 times is an empty string, repeated once remains the same, and so on.

The challenge lies in finding the minimum number of repetitions needed.

Intuition

Let's say a = "abcd" and b = "cdabcdab". The string b isn't immediately a substring of a, but if we repeat a a certain number of times, it can become one.

To find out how many repetitions are needed:

  1. We first calculate the minimum number of times a must be repeated such that the length of the resulting string is equal to or just exceeds the length of b. This is because, for b to be a substring of a, the repeated a must be at least as long as b.

  2. We start by repeating string a this minimum number of times and check if b is a substring of the resultant string. If not, we increment the number of repetitions by one and check again.

  3. We only need to check up to two more repetitions of a beyond the initial calculated number of times. The reasoning is as follows:

    • If b is not a substring of a repeated ans times (where ans is the initial calculated number), b must start near the end of a repeated ans times for it to possibly be included in a further repeated a.
    • If by adding one more a, b is still not a substring, then adding one more repetition on top of that (making it two more repetitions beyond the initial ans) will cover any possible overlap of b as a substring.
  4. If after three attempts (ans, ans+1, and ans+2) b is not a substring, it's concluded that b cannot be made a substring by repeating a.

Thus, the solution lies in trying at most three different numbers of repetitions and checking for the substring condition. If none meet the condition, then we return -1.

Solution Approach

The implementation closely follows the intuition:

  1. First, we measure the lengths of a and b using len(), storing the lengths in variables m and n respectively.

  2. We calculate the initial number of times a needs to be repeated, which we refer to as ans. This is done as follows:

    1ans = ceil(n / m)

    Here, ceil is a mathematical function from the math module that takes a float and rounds it up to the nearest integer. This makes sure that if b is not completely covered by multiples of a, we round up to ensure complete coverage.

  3. Then we initialize a list t that will contain the repeated string a. We multiply the list [a] by ans to repeat the string a that many times initially:

    1t = [a] * ans
  4. Next, we begin testing if b is a substring of the repeatedly joined string a. We use a for loop that runs three times, representing the maximum number of additional repeats we decided would be necessary:

    1for _ in range(3):
    2    if b in ''.join(t):
    3        return ans

    In this loop, we join the elements of t into one string using ''.join(t) and check if b is a substring of this string with b in ''.join(t). If we find b, we immediately return the current number of times a has been repeated (ans).

  5. If b was not found to be a substring, before going for the next loop iteration, we add one more a to our list of strings t, effectively repeating a one more time:

    1    ans += 1
    2    t.append(a)

    We increment ans by 1 for each additional repeat. Continuously checking every time after appending a.

  6. Finally, if three attempts don't result in b becoming a substring, we return -1:

    1return -1

    This is outside our loop and is our default case if b was never found within the repeated a.

Remember, the code doesn't explicitly check ans+2 repetitions within the loop because appending a to t inside the for loop happens at the end of the iteration, which means when the loop exits, we would have already checked up to ans+2 repetitions.

The above code leverages the in operator in Python for substring checking, the join method for concatenation of strings, and a simple list to handle the repetitions. It's a straightforward implementation with the focus on optimizing the number of repetition checks.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have strings a = "xyz" and b = "xyzxyzx". We want to determine how many repetitions of a we need so that b becomes a substring of the repeated a.

Following the solution approach:

  1. We measure the lengths of both strings. For a, the length, m, is 3 and for b, the length, n, is 7.

  2. We calculate the minimum number of times a must be repeated to at least cover the length of b. Using ans = ceil(n / m):

    1ans = ceil(7 / 3) = ceil(2.33) = 3

    The initial number of repetitions of a required is 3.

  3. We prepare our list t to contain the repeated string a. Multiplying the list [a] by ans we get:

    1t = ["xyz", "xyz", "xyz"]
  4. We concatenate strings in t and check if b is a substring.

    After concatenating, we have: ''.join(t) = "xyzxyzxyz"

    Now, we check if b is a substring of this. Since "xyzxyzx" in "xyzxyzxyz" returns True, we've found that b is indeed a substring after the initial number of repetitions.

  5. As a result, we don't need to add more repetitions. The minimum number of repetitions of a needed is 3. We return ans:

    1return 3
  6. If b had not been a substring, we would add another a to t and check again. In this case, it would become ["xyz", "xyz", "xyz", "xyz"] with the concatenated string being "xyzxyzxyzxyz". We would increment ans by 1 and check again.

Since in this example b becomes a substring after the initial number of repetitions, the algorithm finishes early and returns 3.

This process efficiently checks the minimum and only necessary additional repetitions of a to determine if b can become a substring of the repeated a. If the maximum considered repetitions (ans + 2) do not satisfy the condition, the method will conclude with returning -1.

Solution Implementation

1from math import ceil
2
3class Solution:
4    def repeatedStringMatch(self, A: str, B: str) -> int:
5        # Calculate the length of the two strings
6        lenA, lenB = len(A), len(B)
7      
8        # Calculate the minimum number of times A has to be repeated
9        # so that B can possibly be a substring of the repeated A.
10        repetitions = ceil(lenB / lenA)
11      
12        # Create an initial string by repeating A the calculated number of times
13        repeatedA = A * repetitions
14      
15        # Check if B is a substring of the repeated A string
16        # Also allow for B to potentially overlap at the end and beginning of A
17        # by checking one and two additional repeats of A
18        for i in range(3):
19            # If B is found in the current string, return the current count of repetitions
20            if B in repeatedA:
21                return repetitions
22          
23            # If not found, add another A to the end and increment the count
24            repeatedA += A
25            repetitions += 1
26      
27        # If B is not found after the extra checks, return -1 indicating failure
28        return -1
29
1class Solution {
2    public int repeatedStringMatch(String A, String B) {
3        // Calculate the lengths of strings A and B.
4        int lengthA = A.length();
5        int lengthB = B.length();
6      
7        // Calculate the potential minimum number of repetitions required
8        // for string A so that string B becomes a substring of the repeated string A.
9        int repetitions = (lengthB + lengthA - 1) / lengthA;
10      
11        // Build the repeated string by repeating string A as calculated.
12        StringBuilder repeatedString = new StringBuilder(A.repeat(repetitions));
13      
14        // Check up to two additional concatenations of A,
15        // because the substring B could straddle the join of A.
16        for (int i = 0; i < 2; ++i) {
17            // Check if the current repeated string contains string B.
18            if (repeatedString.toString().contains(B)) {
19                // If so, return the number of repetitions used so far.
20                return repetitions;
21            }
22            // Otherwise, increase the number of repetitions and append string A again.
23            repetitions++;
24            repeatedString.append(A);
25        }
26      
27        // If string B was not found after all the iterations, return -1.
28        return -1;
29    }
30}
31
1class Solution {
2public:
3    int repeatedStringMatch(string A, string B) {
4        // Calculate the lengths of strings A and B
5        int lengthA = A.size(), lengthB = B.size();
6      
7        // Calculate the initial repeat count to cover the length of string B
8        int repeatCount = (lengthB + lengthA - 1) / lengthA;
9
10        // Create an empty string t for concatenation
11        string t = "";
12      
13        // Build the initial repeated string with repeatCount times of A
14        for (int i = 0; i < repeatCount; ++i) {
15            t += A;
16        }
17
18        // Check up to 2 more times of string A for the presence of B in t
19        for (int i = 0; i < 2; ++i) {
20          
21            // If string B is found in t, return the current repeat count
22            if (t.find(B) != string::npos) {
23                return repeatCount;
24            }
25
26            // Increase repeat count and append string A to t
27            ++repeatCount;
28            t += A;
29        }
30
31        // If string B was not found, return -1
32        return -1;
33    }
34};
35
1/**
2 * Determines the minimum number of times `pattern` must be repeated such that `target` is a substring of the repeated `pattern`.
3 * If such a repetition is not possible, it returns -1.
4 * 
5 * @param pattern - The string to repeat.
6 * @param target - The string to search for within the repeated `pattern`.
7 * @returns The minimum number of repetitions of `pattern` needed, or -1 if impossible.
8 */
9function repeatedStringMatch(pattern: string, target: string): number {
10    // Length of the input strings 'pattern' and 'target'.
11    const patternLength: number = pattern.length,
12          targetLength: number = target.length;
13
14    // Initial calculation to determine the least number of repetitions.
15    let repetitions: number = Math.ceil(targetLength / patternLength);
16  
17    // `repeatedPattern` stores the repeated string of `pattern`.
18    let repeatedPattern: string = pattern.repeat(repetitions);
19
20    // We check up to 2 times beyond the initial calculated repetitions.
21    // This is because the 'target' could start at the end of one repetition and end at the start of the following.
22    for (let i = 0; i < 3; i++) {
23        // Check if `target` is in the current `repeatedPattern`.
24        if (repeatedPattern.includes(target)) {
25            // If found, return the current count of repetitions.
26            return repetitions;
27        }
28
29        // If not found, increment the repetition count and append `pattern` to `repeatedPattern` again.
30        repetitions++;
31        repeatedPattern += pattern;
32    }
33
34    // If the loop ends and `target` wasn't found in any of the repetitions, return -1.
35    return -1;
36}
37

Time and Space Complexity

The time complexity of the given code can be analyzed based on the operations it performs:

  • The variable assignments and the ceil operation take constant time, hence O(1).
  • Creating t, which is a list of copies of string a, takes O(ans) time in the worst case, as it depends on the initial value of ans, which is ceil(n / m).
  • The for loop will run at most 3 times, with each iteration including a ''.join(t) and testing if b in ''.join(t). The join operation takes O(len(t) * m) because it concatenates len(t) strings of length m. Following this, the in operation has a worst-case time complexity of O((len(t) * m) + n) as it needs to check substring b in the concatenated string.
  • The append operation inside the loop takes O(1) time. However, as the string concatenation inside the loop occurs in each iteration, it increases the total length of the concatenated string by m every time. So, by the third iteration, the join could be operating on a string of length up to 3 * m + (ceil(n / m) * m).

Given these considerations, we estimate the time complexity as:

  • Worst-case time complexity is O((ans + 2) * m + n), reflecting the last iteration of the loop where ans could be incremented twice.

The space complexity is determined by:

  • The space needed by the list t and the strings created by ''.join(t). The maximum length of the joined string can go up to 3 * m + (ceil(n / m) * m).
  • Hence, the worst-case space complexity is O(3 * m + (ceil(n / m) * m)).

Time Complexity: O((ans + 2) * m + n)

Space Complexity: O(3 * m + (ceil(n / m) * m))

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄