Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Repeated String Match

MEDIUMProblemSolveExternal Links

Description

Given two strings a and b, return the minimum number of times you should repeat string a so that string b becomes a substring of the repeated result.

If it is impossible for b to ever be a substring of any number of repetitions of a, return -1.

To clarify what "repeating" means:

  • Repeating "abc" zero times gives ""
  • Repeating "abc" once gives "abc"
  • Repeating "abc" twice gives "abcabc"

Your goal is to find the smallest repetition count k such that b appears somewhere inside the string formed by concatenating a exactly k times.

Examples

Example 1

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

Output: 3

Explanation: When we repeat a three times we get "abcdabcdabcd". The string b = "cdabcdab" appears inside it starting at index 2: "ab[cdabcdab]cd". Two repetitions ("abcdabcd") are not enough because b needs 8 characters starting at position 2, but the text only has 6 characters remaining from that position. Three repetitions is the minimum.

Example 2

Input: a = "a", b = "aa"

Output: 2

Explanation: Repeating a once gives "a", which does not contain "aa". Repeating twice gives "aa", which is exactly b. So the answer is 2.

Example 3

Input: a = "abc", b = "wxyz"

Output: -1

Explanation: No matter how many times we repeat "abc", the resulting string will only contain the characters 'a', 'b', and 'c'. Since b contains 'w', 'x', 'y', and 'z', it can never appear as a substring. Return -1.

Constraints

  • 1 ≤ a.length, b.length ≤ 10^4
  • a and b consist of lowercase English letters.

Editorial

Brute Force

Intuition

The most straightforward way to approach this problem is to literally build the repeated string, one copy of a at a time, and after each addition check whether b has appeared as a substring.

Imagine you are laying down identical tiles end to end on a table. After placing each tile, you check whether a specific pattern drawn on a transparent sheet can be found somewhere across the tiled surface. You keep adding tiles until either the pattern fits or you have laid down so many tiles that adding more cannot possibly help.

The key question is: when do we stop adding copies? Once the repeated string is at least as long as b plus two extra copies of a, we have covered every possible way b could span across copy boundaries. If b is still not found at that point, it will never be found no matter how many more copies we add.

Step-by-Step Explanation

Let's trace through Example 1: a = "abcd", b = "cdabcdab".

Step 1: Start with an empty repeated string. Set count = 0.

Step 2: Append first copy → repeated = "abcd", count = 1. Length 4 < 8 (length of b). The repeated string is too short to even contain b. We must add more.

Step 3: Append second copy → repeated = "abcdabcd", count = 2. Now length is 8 = length of b. Check if b is a substring.

Step 4: Try matching b = "cdabcdab" starting at position 0 in "abcdabcd": text[0]='a' vs b[0]='c' → mismatch. Only position 0 is valid (text length = pattern length), so b is not found with 2 copies.

Step 5: Append third copy → repeated = "abcdabcdabcd", count = 3. Now length is 12. Check again.

Step 6: Try matching at position 0: text[0]='a' ≠ b[0]='c' → fail.

Step 7: Try matching at position 1: text[1]='b' ≠ b[0]='c' → fail.

Step 8: Try matching at position 2: text[2..9] = "cdabcdab" vs b = "cdabcdab" → all 8 characters match! Found!

Step 9: Return count = 3.

Brute Force — Build Repeated String and Search — Watch how we incrementally add copies of string a and attempt to find pattern b as a substring at each stage using naive character comparison.

Algorithm

  1. Initialize an empty string repeated and a counter count = 0.
  2. While the length of repeated is less than len(b) + 2 × len(a):
    a. Append a to repeated and increment count.
    b. If b is found as a substring of repeated (using naive character-by-character comparison at every valid starting position), return count.
  3. If the loop ends without finding b, return -1.

Code

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        string repeated = "";
        int count = 0;
        // Keep adding copies of a until the repeated string
        // is long enough to potentially contain b
        while (repeated.size() < b.size() + 2 * a.size()) {
            repeated += a;
            count++;
            // Naive substring check using built-in find
            if (repeated.find(b) != string::npos) {
                return count;
            }
        }
        return -1;
    }
};
class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        repeated = ""
        count = 0
        # Keep adding copies of a until the repeated string
        # is long enough to potentially contain b
        while len(repeated) < len(b) + 2 * len(a):
            repeated += a
            count += 1
            # Naive substring check
            if b in repeated:
                return count
        return -1
class Solution {
    public int repeatedStringMatch(String a, String b) {
        StringBuilder repeated = new StringBuilder();
        int count = 0;
        // Keep adding copies of a until the repeated string
        // is long enough to potentially contain b
        while (repeated.length() < b.length() + 2 * a.length()) {
            repeated.append(a);
            count++;
            // Naive substring check
            if (repeated.toString().contains(b)) {
                return count;
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n × (n + m))

Where n = len(b) and m = len(a). We build a repeated string of length at most n + 2m. At each of the O(n/m) build steps, we perform a substring check. The built-in substring search uses a naive approach in the worst case, taking O(text_length × pattern_length). The final check on the longest text is O((n + 2m) × n) ≈ O(n² + nm). The dominant cost is this last check, giving us O(n × (n + m)).

Space Complexity: O(n + m)

We store the repeated string which has at most n + 2m characters, giving O(n + m) space.

Why This Approach Is Not Efficient

The brute force relies on a naive substring search that takes O(n × (n + m)) time overall. With n and m both up to 10^4, that is up to roughly 10^8 operations in the worst case — dangerously close to or exceeding typical time limits.

The root cause of inefficiency lies in the substring matching step. Each time the naive matcher encounters a mismatch, it discards all progress and restarts from the very next position. When the pattern has repeating prefixes (like "aaaa" in "aaaa...aaab"), the matcher re-examines the same characters over and over, wasting enormous effort.

Key insight: Algorithms like KMP (Knuth-Morris-Pratt) pre-process the pattern to build a failure function that tells us exactly where to resume matching after a mismatch — the text pointer never moves backward. This reduces the substring search from O(n × m) down to O(n + m), bringing the total time for this problem to O(n + m).

Optimal Approach - KMP String Matching

Intuition

We can split this problem into two independent sub-tasks:

Sub-task 1 — How many repetitions do we need at most?
If b has length n and a has length m, we need at least ⌈n / m⌉ copies of a just to have enough characters. But b might start partway through one copy of a and end partway through another, so we may need one extra copy. The maximum we ever need to check is ⌈n / m⌉ + 1. If b is not found in that many copies, it never will be.

Sub-task 2 — Is b a substring of the repeated string?
Instead of the naive O(n × m) approach, we use the KMP algorithm. KMP pre-processes the pattern b to build a failure function (also called the prefix function). This function answers: when a mismatch occurs at position j of the pattern, what is the longest proper prefix of b[0..j-1] that is also a suffix? We can jump directly to that position instead of starting over from scratch.

The elegant trick is that we do not need to physically build the repeated string at all. We can simulate the repeated string using modular arithmetic: the character at position i of the virtual repeated string is simply a[i % m]. This saves space and avoids costly string concatenation.

Think of it like reading from a circular tape of a — you keep going around the loop, and the KMP automaton tells you how far through pattern b you have matched at each step.

Step-by-Step Explanation

Let's trace Example 1: a = "abcd", b = "cdabcdab".

Step 1: Calculate repetitions. m = 4, n = 8. minReps = ⌈8/4⌉ = 2. maxReps = 2 + 1 = 3. Virtual text length = 3 × 4 = 12.

Step 2: Build KMP failure function for b = "cdabcdab":

  • fail[0] = 0 (by definition)
  • fail[1] = 0 ('d' ≠ 'c')
  • fail[2] = 0 ('a' ≠ 'c')
  • fail[3] = 0 ('b' ≠ 'c')
  • fail[4] = 1 ('c' = 'c', extends prefix)
  • fail[5] = 2 ('d' = 'd', extends "cd")
  • fail[6] = 3 ('a' = 'a', extends "cda")
  • fail[7] = 4 ('b' = 'b', extends "cdab")
  • Result: fail = [0, 0, 0, 0, 1, 2, 3, 4]

Step 3: i=0, j=0: text[0]='a' ≠ pattern[0]='c'. j stays 0, advance i.

Step 4: i=1, j=0: text[1]='b' ≠ pattern[0]='c'. j stays 0, advance i.

Step 5: i=2, j=0: text[2]='c' = pattern[0]='c'. Match! j→1.

Step 6: i=3, j=1: 'd'='d'. j→2. i=4, j=2: 'a'='a'. j→3. i=5, j=3: 'b'='b'. j→4. Consecutive matches advance through the pattern.

Step 7: i=6, j=4: 'c'='c'. j→5. i=7, j=5: 'd'='d'. j→6. The match crosses from the 2nd copy into the 3rd.

Step 8: i=8, j=6: 'a'='a'. j→7. i=9, j=7: 'b'='b'. j→8 = n. Full match!

Step 9: Match found. Position 9 is within the first 3 copies (positions 0–11). Return 3.

KMP Matching on Virtual Repeated String — Watch the KMP algorithm scan through the virtual repeated string character by character, never backtracking in the text. The failure function allows instant recovery from mismatches.

Algorithm

  1. Let m = len(a), n = len(b). Compute minReps = ⌈n / m⌉ and maxReps = minReps + 1.
  2. Build the KMP failure function for pattern b:
    • Initialize fail array of size n with all zeros.
    • For each position i from 1 to n - 1: follow the failure chain until a match or j reaches 0. If b[i] == b[j], increment j. Set fail[i] = j.
  3. For reps from minReps to maxReps:
    a. Set textLen = reps × m.
    b. Run KMP matching: scan i from 0 to textLen - 1, using a[i % m] as the text character (virtual repeated string, no physical concatenation needed).
    c. For each i, advance j using the failure function. If j reaches n, pattern is found — return reps.
  4. If no match found after trying maxReps, return -1.

Code

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int m = a.size(), n = b.size();
        int minReps = (n + m - 1) / m; // ceil(n / m)
        
        // Build KMP failure function for pattern b
        vector<int> fail(n, 0);
        for (int i = 1; i < n; i++) {
            int j = fail[i - 1];
            while (j > 0 && b[i] != b[j]) j = fail[j - 1];
            if (b[i] == b[j]) j++;
            fail[i] = j;
        }
        
        // Try minReps and minReps + 1 repetitions
        for (int reps = minReps; reps <= minReps + 1; reps++) {
            int textLen = reps * m;
            int j = 0;
            for (int i = 0; i < textLen; i++) {
                char c = a[i % m]; // Virtual repeated string
                while (j > 0 && c != b[j]) j = fail[j - 1];
                if (c == b[j]) j++;
                if (j == n) return reps;
            }
        }
        return -1;
    }
};
class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        m, n = len(a), len(b)
        min_reps = (n + m - 1) // m  # ceil(n / m)
        
        # Build KMP failure function for pattern b
        fail = [0] * n
        for i in range(1, n):
            j = fail[i - 1]
            while j > 0 and b[i] != b[j]:
                j = fail[j - 1]
            if b[i] == b[j]:
                j += 1
            fail[i] = j
        
        # Try min_reps and min_reps + 1 repetitions
        for reps in range(min_reps, min_reps + 2):
            text_len = reps * m
            j = 0
            for i in range(text_len):
                c = a[i % m]  # Virtual repeated string
                while j > 0 and c != b[j]:
                    j = fail[j - 1]
                if c == b[j]:
                    j += 1
                if j == n:
                    return reps
        return -1
class Solution {
    public int repeatedStringMatch(String a, String b) {
        int m = a.length(), n = b.length();
        int minReps = (n + m - 1) / m; // ceil(n / m)
        
        // Build KMP failure function for pattern b
        int[] fail = new int[n];
        for (int i = 1; i < n; i++) {
            int j = fail[i - 1];
            while (j > 0 && b.charAt(i) != b.charAt(j)) j = fail[j - 1];
            if (b.charAt(i) == b.charAt(j)) j++;
            fail[i] = j;
        }
        
        // Try minReps and minReps + 1 repetitions
        for (int reps = minReps; reps <= minReps + 1; reps++) {
            int textLen = reps * m;
            int j = 0;
            for (int i = 0; i < textLen; i++) {
                char c = a.charAt(i % m); // Virtual repeated string
                while (j > 0 && c != b.charAt(j)) j = fail[j - 1];
                if (c == b.charAt(j)) j++;
                if (j == n) return reps;
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n + m)

Where n = len(b) and m = len(a). Building the KMP failure function takes O(n). The matching phase scans a virtual text of length at most (⌈n/m⌉ + 1) × m = O(n + m) characters. Each character is examined at most twice (once by the main scan and at most once by the failure fallback), so matching is O(n + m). The total is O(n + m).

Space Complexity: O(n)

The KMP failure array requires O(n) space. We do not physically build the repeated string — instead we use a[i % m] to access characters virtually, so no extra O(n + m) text storage is needed. The only auxiliary data structure is the failure array of size n.