algoadvance

Leetcode 686. Repeated String Match

Problem Statement

Given two strings a and b, return the minimum number of times that string a has to be repeated such that b is a substring of the repeated string. If no such solution, return -1.

For example, if a = "abcd" and b = "cdabcdab", return 3 because by repeating a three times (“abcdabcdabcd”), b is a substring of the repeated string.

Clarifying Questions

  1. Can we assume both a and b are non-empty strings?
    • Yes, you can assume that both a and b are non-empty.
  2. Is there a length constraint on the strings a and b?
    • You can assume the lengths of a and b are within a reasonable limit, typically up to 1000 characters.
  3. What should be returned if a cannot be repeated enough times to contain b as a substring?
    • Return -1 if it is impossible for b to be a substring of the repeated a.

Strategy

To solve this problem, there are a few steps involved:

  1. Concatenation (Base Case): Given a and b, if b is already a substring of a, then you need to return 1.
  2. Concatenate a multiple times: We’ll repeatedly concatenate a until the length of the concatenated string is at least the length of b.
  3. Check Substring: Check if b is a substring of this concatenated string.
  4. Incrementally Add a: If not found, continue to add one more a and check again.
  5. Stopping Condition: At most, you need to repeat a such that the length of the concatenated string is just over twice the length of b. This is because if b is not found within 2 lengths of its own size in any constructed string of repeated a, it means repeating further will not help.

Code

Here’s the implementation in Java:

public class Solution {
    public int repeatedStringMatch(String a, String b) {
        int lenA = a.length();
        int lenB = b.length();
        
        StringBuilder repeatedA = new StringBuilder();
        int count = 0;
        
        // Repeat until the length of repeatedA is at least lenB
        while (repeatedA.length() < lenB) {
            repeatedA.append(a);
            count++;
        }
        
        // Check if b is a substring of the currently built string
        if (repeatedA.toString().contains(b)) {
            return count;
        }
        
        // Append once more and check again
        repeatedA.append(a);
        count++;
        if (repeatedA.toString().contains(b)) {
            return count;
        }
        
        // If not found, return -1
        return -1;
    }
}

Time Complexity

Therefore, the overall time complexity is (O(N \cdot M)), where checking for the substring dominates the complexity. The space complexity is influenced by the length of the concatenated string, which would be (O(N \cdot (\frac{2M}{N} + 1))).

By following this procedure, we ensure the minimum number of repeats necessary to see if b can be a substring, and we efficiently return the minimum count or -1 if not possible.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI