Repeated String Match (LeetCode 686)

The problem

You get two strings a and b. Return the smallest number of times you must repeat a (glue copies end to end) so that b becomes a substring of the result. If no number of repeats works, return -1.

Input:  a = "abcd", b = "cdabcdab"
Output: 3

Three copies give "abcdabcdabcd", which contains "cdabcdab" starting at index 2. Two copies ("abcdabcd") are not enough.

How to think about it

Start with brute force. Keep appending a and checking whether b is inside, forever. The question is when to stop and say -1. Without a bound, this never terminates on an impossible input.

The key insight: only two counts are worth checking. Let q be the smallest count with len(a) * q >= len(b). You need at least q copies just to have enough characters. If b fits anywhere, it starts somewhere inside the first copy of a (any later start is the same as one inside the first copy). Starting inside the first copy and running for len(b) characters, it spills into at most one extra copy. So the answer is q or q + 1, or impossible.

Why more copies never help. The repeated string is periodic with period len(a). Once you’ve tried every starting offset (q + 1 copies covers them all), adding copies only adds more of the same pattern.

Which pattern is this? Bounded string matching. The tell is “repeat a string until something matches”: find the bound where repetition stops adding new possibilities.

Approach

1. Start with s = a and count = 1.
2. While len(s) < len(b), append a and add one to count. Now count is q.
3. If b in s, return count.
4. If b in s + a, return count + 1: b straddled one more copy.
5. Otherwise return -1.

Solution

def repeatedStringMatch(a, b):
    count = 1; s = a
    while len(s) < len(b):          # minimum copies to be long enough
        s += a; count += 1
    if b in s:
        return count
    if b in s + a:            # b may straddle one more copy
        return count + 1
    return -1
# repeatedStringMatch("abcd", "cdabcdab") -> 3

Dry run

On a = "abcd", b = "cdabcdab" (length 8):

b starts at the c of the first copy, so it needs part of a third copy to finish.

Complexity

• Time: O(n + m) with a linear substring search, where n = len(a) and m = len(b). The built string has length at most m + 2n. CPython’s in is fast in practice; a KMP search guarantees the bound.
• Space: O(n + m). For the built string.

Edge cases and pitfalls

• b shorter than a: the loop doesn’t run, and you still need the s + a check, since b may straddle the seam (a = "abc", b = "ca" needs 2).
• Characters in b not in a give -1 quickly: a = "abc", b = "wxyz" returns -1.
• Exactly equal lengths still need the extra-copy check: a = "abc", b = "cab" returns 2.
• Looping “until it matches” with no bound hangs on impossible input. State the q + 1 bound in the interview.
• a = "a", b = "aa" returns 2; the loop handles it.

Related problems

• Find the Index of the First Occurrence in a String (LeetCode 28): the substring search underneath in.
• Repeated Substring Pattern (LeetCode 459): the doubled-string trick for periodic strings.
• Shortest Palindrome (LeetCode 214): another problem about gluing strings together and matching.