Repeated String Match

Leetcode Problem 686: Repeated String Match

Problem Summary

Given two strings a and b, return the minimum number of times a has to be repeated so that b becomes a substring of the resulting text. If no number of repetitions works, return -1. Both strings are at most ten thousand characters long and consist of lowercase English letters.

The difficulty is that the candidate text is unbounded, so the search space has to be cut down before any matching happens. Two arguments do it. Since a text shorter than b cannot contain b, at least the ceiling of the ratio between the two lengths is needed. Since the repetition is periodic with period equal to the length of a, any occurrence can be shifted back until it starts inside the first copy, and an occurrence starting there spans at most one block beyond the copies that cover its own length. Only two candidate counts therefore need to be tested, and everything beyond them is provably useless.

Techniques

• String
• String Matching

Solution

function repeatedStringMatch(a: string, b: string): number {
    // b needs at least enough copies of a to cover its own length
    const minimumCopies = Math.ceil(b.length / a.length)
    const repeated = a.repeat(minimumCopies)

    if (repeated.includes(b)) {
        return minimumCopies
    }

    // one extra copy is the most that can help, since it covers any offset into the first block
    if ((repeated + a).includes(b)) {
        return minimumCopies + 1
    }

    return -1
};