Minimum repeat to make substring

Given two strings s1 and s2. Return a minimum number of times s1 has to be repeated such that s2 is a substring of it. If s2 can never be a substring then return -1.

Note: Both the strings contain only lowercase letters.

Examples:

Input: s1 = "ww", s2 = "www"
Output: 2
Explanation: Repeating s1 two times (wwww), s2 is a substring of it.

Input: s1 = "abcd", s2 = "cdabcdab" 
Output: 3 
Explanation: Repeating s1 three times (abcdabcdabcd), s2 is a substring of it. s2 is not a substring of s2 when it is repeated less than 3 times.

Input: s1 = "ab", s2 = "cab"
Output: -1
Explanation: No matter how many times we repeat s1, we can't get a string such that s2 is a substring of it.

Constraints:
1 ≤ |s1|, |s2| ≤ 10⁵

Approach 01:

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    void computeLPSArray(vector<int>& lps, const string& pattern) {
        lps[0] = 0;
        int prefixIndex = 0, suffixIndex = 1;
    
        // Building the LPS (Longest Prefix Suffix) array
        while (suffixIndex < pattern.size()) {
            if (pattern[prefixIndex] == pattern[suffixIndex]) {
                lps[suffixIndex] = prefixIndex + 1;
                prefixIndex++;
                suffixIndex++;
            } else {
                if (prefixIndex == 0) {
                    lps[suffixIndex] = 0;
                    suffixIndex++;
                } else {
                    prefixIndex = lps[prefixIndex - 1];
                }
            }
        }
    }
    
    bool kmpSearch(const string& text, const string& pattern) {
        vector<int> lps(pattern.size(), 0);
        computeLPSArray(lps, pattern);
    
        int textIndex = 0, patternIndex = 0;
    
        // Performing KMP search
        while (patternIndex < pattern.size() && textIndex < text.size()) {
            if (pattern[patternIndex] == text[textIndex]) {
                textIndex++;
                patternIndex++;
            } else {
                if (patternIndex == 0) {
                    textIndex++;
                } else {
                    patternIndex = lps[patternIndex - 1];
                }
            }
        }
    
        return patternIndex == pattern.size();
    }
    
    int minRepeats(string& strA, string& strB) {
        if (strA == strB) return 1;
    
        int repeatCount = 1;
        string repeatedStr = strA;
    
        // Repeat strA until its length is at least the length of strB
        while (repeatedStr.size() < strB.size()) {
            repeatedStr += strA;
            repeatCount++;
        }
    
        // Check if strB is a substring using KMP
        if (kmpSearch(repeatedStr, strB)) return repeatCount;
    
        // Check with one more repetition
        if (kmpSearch(repeatedStr + strA, strB)) return repeatCount + 1;
    
        return -1;
    }

};

class Solution:
    def computeLPSArray(self, pattern: str) -> list:
        lps = [0] * len(pattern)
        prefixIndex = 0
        suffixIndex = 1

        # Building the LPS (Longest Prefix Suffix) array
        while suffixIndex < len(pattern):
            if pattern[prefixIndex] == pattern[suffixIndex]:
                lps[suffixIndex] = prefixIndex + 1
                prefixIndex += 1
                suffixIndex += 1
            else:
                if prefixIndex == 0:
                    lps[suffixIndex] = 0
                    suffixIndex += 1
                else:
                    prefixIndex = lps[prefixIndex - 1]
        return lps

    def kmpSearch(self, text: str, pattern: str) -> bool:
        lps = self.computeLPSArray(pattern)
        textIndex = 0
        patternIndex = 0

        # Performing KMP search
        while patternIndex < len(pattern) and textIndex < len(text):
            if pattern[patternIndex] == text[textIndex]:
                textIndex += 1
                patternIndex += 1
            else:
                if patternIndex == 0:
                    textIndex += 1
                else:
                    patternIndex = lps[patternIndex - 1]

        return patternIndex == len(pattern)

    def minRepeats(self, strA: str, strB: str) -> int:
        if strA == strB:
            return 1

        repeatCount = 1
        repeatedStr = strA

        # Repeat strA until its length is at least the length of strB
        while len(repeatedStr) < len(strB):
            repeatedStr += strA
            repeatCount += 1

        # Check if strB is a substring using KMP
        if self.kmpSearch(repeatedStr, strB):
            return repeatCount

        # Check with one more repetition
        if self.kmpSearch(repeatedStr + strA, strB):
            return repeatCount + 1

        return -1

Time Complexity

• LPS Array Computation:

  The computeLPSArray function takes \( O(M) \) time, where \( M \) is the length of the pattern strB, to build the LPS (Longest Prefix Suffix) array.

• KMP Search:

  The kmpSearch function takes \( O(N + M) \) time, where \( N \) is the length of the text repeatedStr and \( M \) is the length of the pattern strB. This is because the KMP algorithm ensures that each character of the text and pattern is compared at most once.

• Repeating and Concatenating Strings:

  In the minRepeats function, we repeat strA until its length is at least the length of strB. This process takes \( O(K) \) time, where \( K \) is the total length of the concatenated string. Additionally, checking kmpSearch twice (once with the initial repetition and once with one additional repetition) takes \( O(K + M) \).

• Overall Time Complexity:

  The overall time complexity is dominated by the concatenation and KMP search, which results in \( O(K + M) \). Here, \( K \) is approximately \( M \times R \), where \( R \) is the number of repetitions needed.

Space Complexity

• LPS Array:

  The function uses an LPS array of size \( M \), where \( M \) is the length of strB. This requires \( O(M) \) space.

• Repeated String:

  The repeatedStr variable takes up \( O(K) \) space, where \( K \) is the length of the repeated string.

• Auxiliary Variables:

  The function uses a few variables like repeatCount, textIndex, and patternIndex, which take up constant space \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(K + M) \) due to the repeated string and the LPS array.