Minimum repeat to make substring

JavaView on GFG

Intuition

Find minimum repetitions of string A to make B a substring. KMP or brute force.

Algorithm

1Minimum repeats = ceil(len(B)/len(A)). Try this many and one more repetition. Use KMP to check if B is substring.

Common Pitfalls

•Same as LC 686. Try repeating A exactly ceil(|B|/|A|) and ceil(|B|/|A|)+1 times. KMP search.

Minimum repeat to make substring.java

Java

// Approach: Repeat s until length >= len(target)*2. Check if target is a substring of repeated s.
// Time: O(n * m) Space: O(n)
class Solution {
    static int minRepeats(String s1, String s2) {
        StringBuilder str = new StringBuilder(s1);

        for (int i = 0; i < s2.length(); i++) {
            if (!s1.contains("" + s2.charAt(i)))
                return -1;
        }

        int count = 0;
        while (str.length() < 4 * s2.length()) {
            count++;
            if (str.toString().contains(s2))
                return count;

            str.append(s1);
        }

        return -1;
    }
};

Was this solution helpful?