Repeated String Match

Description

686. Repeated String Match

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b to be a substring of a after repeating it, return -1.

Notice: String "abc" repeated 0 times is "", repeated 1 time is "abc", and repeated 2 times is "abcabc".

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\le \text{a.length},\text{b.length}\le 10^4$
• a and b consist of lowercase English letters.

---

Approach 1: Length-Bound Simulation ($O(N\times M)$ Time, $O(N+M)$ Space)

Intuition

1. Repeat string a until its total length is at least as long as string b. Keep track of the repeat count.
2. If b is a substring of this repeated a, return the current count.
3. Otherwise, append a one additional time to cover potential boundary overlaps (where b starts near the end of a and wraps around to the beginning of a). Check again.
4. If b is still not found after this single extra repeat, it will never be possible, so return -1.

class Solution {
    public int repeatedStringMatch(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
 
        // Step 1: Append 'a' until string length >= b.length()
        while (sb.length() < b.length()) {
            sb.append(a);
            count++;
        }
 
        // Step 2: Check if b is a substring
        if (sb.indexOf(b) != -1) {
            return count;
        }
 
        // Step 3: Append 'a' one more time for boundary overlaps
        sb.append(a);
        count++;
 
        if (sb.indexOf(b) != -1) {
            return count;
        }
 
        return -1;
    }
}
 

Complexity

• Time Complexity: $O(N\times M)$ — Where $N=\text{a.length}$ and $M=\text{b.length}$. Constructing the string takes $O(N+M)$, while built-in indexOf pattern matching takes $O(N\times M)$ worst-case time.
• Space Complexity: $O(N+M)$ — To store the repeated string in memory.

---

Approach 2: KMP Algorithm (Optimal — $O(N+M)$ Time, $O(M)$ Space)

Intuition

To guarantee linear $O(N+M)$ time complexity without relying on generic substring search:

1. Construct the Longest Prefix Suffix (LPS) array for pattern b.
2. Search for pattern b inside a treated as an infinite stream (using modular indexing i % a.length()).
3. Maintain a counter of how many total characters in a have been consumed. Once the entire pattern b is matched, calculate the minimum number of repeats of a needed to cover that character range.

class Solution {
    public int repeatedStringMatch(String a, String b) {
        int n = a.length();
        int m = b.length();
 
        // Step 1: Compute LPS array for string b
        int[] lps = computeLPS(b);
 
        // Step 2: KMP Search over virtual repeated string 'a'
        int i = 0; // Pointer for string a (virtual stream)
        int j = 0; // Pointer for pattern b
 
        // Maximum character checks needed to cover all overlap positions
        while (i < n + m + n) {
            if (a.charAt(i % n) == b.charAt(j)) {
                i++;
                j++;
                if (j == m) {
                    // Match found! Calculate total repeats used
                    return (int) Math.ceil((double) i / n);
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
 
        return -1;
    }
 
    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
 
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
 
        return lps;
    }
}
 

Complexity

• Time Complexity: $O(N+M)$ — Precomputing LPS takes $O(M)$ and the KMP search traverses at most $2N+M$ character checks in $O(N+M)$ time.
• Space Complexity: $O(M)$ — For the LPS lookup table of pattern b.

---

Easy Memory Rule

“Repeat a until length $\ge b.length()$. Check indexOf(b) now, and check once more with one extra a. If neither works, return -1!”

Prefix

A prefix is a part of a string that starts from the beginning of the string.
Example: ABCDE
Prefixes:
A, AB, ABC, ABCD, ABCDE

Suffix

A suffix is a part of a string that ends at the end of the string.
Example: ABCDE
Suffixes:
E, DE, CDE, BCDE, ABCDE

Proper Prefix / Suffix

A proper prefix/suffix is a prefix or suffix that is not the entire string.
For ABCDE:

• ABCDE → prefix and suffix, but not a proper prefix/suffix
• ABC → proper prefix
• CDE → proper suffix
  We don’t consider the entire string because otherwise every string would always have itself as both a prefix and suffix.

LPS (Longest Prefix Suffix)

LPS = Longest Proper Prefix which is also a Suffix.
In other words:

Find the longest part that appears at both the beginning and end of the string, excluding the whole string.

Example: ABAB

• Prefixes: A, AB, ABA

• Suffixes: B, AB, BAB

• Common: AB

• Therefore, LPS = 2 (length of AB)

• We have a prefix-window on the left and a suffix-window ending at i; len is their current matching length. If the next characters match, extend the windows; if they don’t, shrink to the largest smaller prefix that can still overlap.

What is LPS?

LPS stands for Longest Prefix Suffix.
In the KMP algorithm, lps[i] stores the length of the longest proper prefix of the substring pattern[0...i] that is also a suffix of that same substring.

• Prefix: A substring starting at index 0.
• Suffix: A substring ending at index i.
• Proper Prefix: A prefix that is not equal to the whole string itself.

Example: pattern = "ABABC"

• For "A" (len 1): Prefix = "", Suffix = "" $\to$ lps[0] = 0
• For "AB" (len 2): Prefix = "A", Suffix = "B" $\to$ lps[1] = 0
• For "ABA" (len 3): Prefix = "A", Suffix = "A" $\to$ lps[2] = 1
• For "ABAB" (len 4): Prefix = "AB", Suffix = "AB" $\to$ lps[3] = 2
• For "ABABC" (len 5): No matching prefix/suffix $\to$ lps[4] = 0

---

How to Compute LPS ($O(M)$ Time)

We maintain two pointers:

• i: Moves forward through the string (starts at 1).
• len: Stores the length of the previous longest prefix-suffix (starts at 0).

Algorithm Logic:

1. Set lps[0] = 0.
2. If pattern[i] == pattern[len]:
   • len++
   • lps[i] = len
   • i++
3. If pattern[i] != pattern[len]:
   • If len != 0: Backtrack len = lps[len - 1] (do not increment i).
   • If len == 0: Set lps[i] = 0, then i++.

KMP

while (i < text.length()) {
 
    if (text.charAt(i) == pattern.charAt(j)) {
        i++;
        j++;
 
        if (j == pattern.length()) {
            // pattern found
        }
 
    } else {
 
        if (j != 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
}