algoadvance

Leetcode 686. Repeated String Match

Problem Statement

686. 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 the repeated string. If it is impossible for b to be a substring of the repeated a, return -1.

Example 1:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We need to repeat "abcd" three times to get "abcdabcdabcd", which contains "cdabcdab".

Example 2:

Input: a = "a", b = "aa"
Output: 2
Explanation: We need to repeat "a" two times to get "aa", which contains "aa".

Constraints:

Clarifying Questions

  1. Q: Are the strings guaranteed to consist of only lowercase English letters?
    • A: Yes.
  2. Q: Can a and b be of equal length?
    • A: Yes, and they can also be different.
  3. Q: Does the repetition of a need to be contiguous to form b?
    • A: Yes, the repetition of a should ensure that b is a contiguous substring within the repeated string formed by a.

Strategy

  1. Initial Repeat Count:
    • Start by calculating the minimum number of repetitions of a that would cover the length of b. This would be ceil(len(b) / len(a)).
  2. Checking Substring Presence:
    • We consider repeating string a an extra time (or two), because there may be overlap where b starts at the end of one repetition of a and continues into the beginning of the next.
  3. Implementation Steps:
    • Repeat a at most ceil(len(b) / len(a)) + 2 times and check if b is a substring within these repetitions.
    • If found, return the number of repetitions.
    • If not found after the maximum number of practical repetitions, return -1.

Code

#include <iostream>
#include <string>
#include <cmath>

class Solution {
public:
    int repeatedStringMatch(std::string a, std::string b) {
        int repeatedCount = std::ceil((double)b.size() / a.size());
        std::string repeatedA = a;
        
        // Initial repeated string to cover length of b
        for (int i = 1; i < repeatedCount; ++i) {
            repeatedA += a;
        }

        // Check if b is a substring of current repeatedA
        if (repeatedA.find(b) != std::string::npos) return repeatedCount;
        
        // Add one more repetition of a to check
        repeatedA += a;
        if (repeatedA.find(b) != std::string::npos) return repeatedCount + 1;
        
        // Add two repetitions of a to consider edge overlaps
        repeatedA += a;
        if (repeatedA.find(b) != std::string::npos) return repeatedCount + 2;
        
        // If still not found
        return -1;
    }
};

int main() {
    Solution sol;
    std::string a = "abcd";
    std::string b = "cdabcdab";
    std::cout << sol.repeatedStringMatch(a, b); // Output: 3
    return 0;
}

Time Complexity

Overall, the time complexity is ( O(n \times m) ).

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