Repeated String Match

Problem Statement

The task is to determine the minimum number of times string 'a' needs to be repeated such that string 'b' becomes a substring of the resulting string. The solution should return an integer indicating how many times 'a' should be repeated. If it is impossible for 'b' to ever be a substring of 'a' after any number of repetitions, the function should return -1. This challenge emphasizes understanding the manipulation of strings and substrings, as well as considerations on the repetition of patterns within a string context.

Examples

Example 1

Input:

a = "abcd", b = "cdabcdab"

Output:

3

Explanation:

We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

Example 2

Input:

a = "a", b = "aa"

Output:

2

Constraints

• 1 <= a.length, b.length <= 104
• a and b consist of lowercase English letters.

Approach and Intuition

To solve this problem, we can employ a straightforward approach with a little bit of intuition on string manipulation:

1. Begin by understanding the relationship between the two strings. If 'b' contains characters that are not in 'a', it's immediately apparent that no amount of repetition will make 'b' a substring of repeated 'a'. In this case, return -1.

2. Check if repeating 'a' can incrementally build up to include 'b':

   • Start by repeating 'a' until the length of the repeated string is greater than or equal to 'b'. This is your base case for the minimal repeat.
   • Observe whether 'b' becomes a substring in this or fewer repetitions. Since concatenating a string involves increasing its length in blocks of itself, determine the shortest repetition where 'b' fits.

3. Implement a check using simple iteration:

   • Construct a string by repeating 'a' increasingly until the repeated string includes 'b' as a substring or until adding more repetitions still fails to achieve this. Given the constraints, this process efficiently determines the minimal repetition.
   • A consideration here lies in checking lengths sufficiently. As 'b' can be longer than 'a', but still be formed by some pattern in 'a', we may need to check by repeating 'a' several times. In the worst-case scenario, repeating 'a' up to twice its length relative to 'b' should suffice.

4. Calculate using the most direct approach:

   • Repeat 'a' and check for the presence of 'b' until reaching the necessary number of repetitions. Utilize string operations available in most programming languages to handle these checks. This mechanism, although not optimized for performance complexities involving extremely long strings and numerous repetitions, covers typical constraints efficiently.

By understanding the constraints and behavior of strings when repeated, this method provides a comprehensible and effective solution to the problem presented.

Solutions

import java.math.BigInteger;

class Solution {
    public boolean isSubsequenceRotated(int startPos, String mainStr, String targetStr) {
        for (int j = 0; j < targetStr.length(); j++) {
            if (mainStr.charAt((j + startPos) % mainStr.length()) != targetStr.charAt(j)) {
                return false;
            }
        }
        return true;
    }
    public int countRepeatsRequired(String primaryStr, String secondaryStr) {
        int neededRepeats = (secondaryStr.length() - 1) / primaryStr.length() + 1;
        int primeBase = 113, MODULO = 1_000_000_007;
        int primeInverse = BigInteger.valueOf(primeBase).modInverse(BigInteger.valueOf(MODULO)).intValue();

        long hashSecondary = 0, powerMultiplier = 1;
        for (int i = 0; i < secondaryStr.length(); i++) {
            hashSecondary += powerMultiplier * secondaryStr.codePointAt(i);
            hashSecondary %= MODULO;
            powerMultiplier = (powerMultiplier * primeBase) % MODULO;
        }

        long hashPrimary = 0; powerMultiplier = 1;
        for (int i = 0; i < secondaryStr.length(); i++) {
            hashPrimary += powerMultiplier * primaryStr.codePointAt(i % primaryStr.length());
            hashPrimary %= MODULO;
            powerMultiplier = (powerMultiplier * primeBase) % MODULO;
        }

        if (hashPrimary == hashSecondary && isSubsequenceRotated(0, primaryStr, secondaryStr)) return neededRepeats;
        powerMultiplier = (powerMultiplier * primeInverse) % MODULO;

        for (int i = secondaryStr.length(); i < (neededRepeats + 1) * primaryStr.length(); i++) {
            hashPrimary -= primaryStr.codePointAt((i - secondaryStr.length()) % primaryStr.length());
            hashPrimary *= primeInverse;
            hashPrimary += powerMultiplier * primaryStr.codePointAt(i % primaryStr.length());
            hashPrimary %= MODULO;
            if (hashPrimary == hashSecondary && isSubsequenceRotated(i - secondaryStr.length() + 1, primaryStr, secondaryStr)) {
                return i < neededRepeats * primaryStr.length() ? neededRepeats : neededRepeats + 1;
            }
        }
        return -1;
    }
}