Repeated String Match

Problem

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

For example, with A = "abcd" and B = "cdabcdab".

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").

Note: The length of A and B will be between 1 and 10000.

Solution

StringBuilder Solution

public class Solution {
    public int repeatedStringMatch(String a, String b) {
        int count = 0;
        StringBuilder sb = new StringBuilder();
        while (sb.length() < b.length()) {
            count++;
            sb.append(a);
        }
        if (sb.toString().contains(b)) return count;
        if (sb.append(a).toString().contains(b)) return count + 1;
        return -1;
    }
}

Two Pointers Solution

public class Solution {
    public int repeatedStringMatch(String a, String b) {
        int i = 0, j = 0;
        while (i < a.length()) {
            j = 0;
            while (j < b.length() && a.charAt((i + j) % a.length()) == b.charAt(j)) j++;
            if (j == b.length()) {
                int extra = (i + j) % a.length() == 0 ? 0 : 1;
                return (i + j) / a.length() + extra;
            }
            i++;
        }
        return -1;
    }
}

Analysis

If b is only consisted of a, the worst case is that it has some leftover in left side and right side
Hence, we need to add one more time of a to get the correct result
That's why we call sb.append(a) and see if it contains(b) and return count + 1

In the second solution, we use kind of greedy idea
We loop through a as the starting repeated character of b
Then we check if from that starting character, b has exact same pattern
To get the correct index from a, we use (i + j) % a.length()
And if we find the exact same pattern in b, which means j == b.length()
We need to check if there needs one extra repeated, which is (i + j) % a.length() == 0
If it's not 0, we know i does not end at the end of a, hence we need to plus 1
At the end, we return how many times the pattern repeated as (i + j) / a.length() + extra