Repeated String Match in C++ (LeetCode 686): Brute Force, String Matching & KMP Approaches

Understanding string manipulation and pattern matching is a fundamental skill for any software engineer. Among the many string problems you will encounter, LeetCode 686 – Repeated String Match stands out because it tests more than just your ability to find a substring. It tests your logical reasoning regarding boundaries, modular repeating structures, and cyclic string properties.

Interviewers love this problem. On the surface, it looks like a simple string search. However, the catch lies in knowing exactly when to stop repeating the base string. If you don't establish a hard mathematical boundary, your program will either fail on edge cases or run into an infinite loop, resulting in a Memory Limit Exceeded (MLE) or Time Limit Exceeded (TLE) error.

In this comprehensive tutorial, we will break down the Repeated String Match solution from scratch. Whether you are preparing for a coding interview or just sharpening your C++ String Problems toolkit, you will learn how to transition from a naive brute force loop to an optimized std::string::find() approach, and finally to an enterprise-grade KMP (Knuth-Morris-Pratt) algorithm.

Problem Statement

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

If it is impossible for b to be a substring of a no matter how many times you repeat it, return -1.

Note: A repeated string is simply the original string concatenated with itself. For example, if a = "abc", repeating it 0 times yields "", repeating it 1 time yields "abc", and repeating it 2 times yields "abcabc".

Constraints

Before writing any code, always analyze the constraints to determine what time complexity is acceptable.

• 1 <= a.length, b.length <= 10000
• a and b consist of lowercase English letters.

Because the strings can be up to 10,000 characters long, an $O(N^2)$ algorithm might struggle or time out. We should aim for an algorithm that operates in linear or near-linear time relative to the lengths of the strings.

Examples

Here is a breakdown of various inputs and their expected outputs to help solidify your understanding.

Intuition

The core of the Repeated String Match algorithm relies on understanding bounds.

If b is going to be a substring of a repeated a, how many copies of a do we actually need? Let's think about the physical length of the strings. For b to fit inside a repeated version of a, the total length of the repeated string must be at least the length of b.

Let q be the minimum number of times we must repeat a so its length equals or exceeds b. Mathematically, this is the ceiling of b.length() / a.length().

Now, if b is indeed a valid substring, it must begin somewhere inside the very first copy of a. Because it starts inside that first copy, it can stretch across the subsequent copies.

• Case 1: It starts exactly at the beginning of a and ends perfectly within q copies.
• Case 2: It starts somewhere in the middle of the first copy of a. Because it is offset, it will "spill over" the end of the q-th copy, requiring exactly one more copy of a to accommodate the tail end of b.

Therefore, the matching string can only ever require q repetitions or q + 1 repetitions. If b is not found in q + 1 repetitions, adding a q + 2 copy will not magically create a match. At that point, you have exhausted all possible starting positions within the first copy of a.

Dry Run

Approach 1: Brute Force

Intuition

The most naive way to solve this is to simply keep appending a to a temporary string and checking if b is a substring after every single append operation. To prevent an infinite loop, we cap the iterations based on our boundary logic: we stop when the length of our temporary string exceeds b.length() + a.length().

Algorithm

1. Initialize an empty string temp and a repetition counter count = 0.
2. Enter a while loop that runs as long as temp.length() < b.length().
3. In each iteration, append a to temp and increment count.
4. Once temp is long enough, check if b is a substring. If it is, return count.
5. If not, append a one last time, increment count, and check again.
6. If both checks fail, return -1.

#include <string>

using namespace std;

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        string temp = "";
        int count = 0;
        
        // Keep appending until temp is at least as long as b
        while (temp.length() < b.length()) {
            temp += a;
            count++;
        }
        
        // Check if b is present in the current string
        if (temp.find(b) != string::npos) {
            return count;
        }
        
        // Append one more time for the "spillover" case
        temp += a;
        count++;
        
        if (temp.find(b) != string::npos) {
            return count;
        }
        
        return -1;
    }
};

Complexity Analysis

• Time Complexity: $O(N \cdot (N + M))$, where $N$ is the length of a and $M$ is the length of b. String concatenation and find() inside a loop create a significant overhead. The built-in find() operates in $O(T \cdot P)$ worst-case, meaning repeated checks get expensive.
• Space Complexity: $O(N + M)$ to store the concatenated string.

Advantages

• Extremely easy to read and understand.
• Simple to write under interview pressure if you blank on the optimal math.

Disadvantages

• Slow execution time due to repeated string reallocations and searching from scratch multiple times.

Approach 2: Using std::string::find() (Optimal Interview Solution)

Intuition

Instead of appending in a while loop and doing multiple checks, we can use math to jump straight to the exact string we need. We pre-calculate q, build the string once, and check exactly twice. This approach is highly recommended for a standard coding interview because it balances performance with clean, bug-free implementation.

Algorithm

1. Calculate q, the base number of repetitions required: b.length() / a.length(). If there is a remainder, add 1.
2. Build a string repeatedA by repeating a exactly q times.
3. Check if b is in repeatedA. If yes, return q.
4. Append a one more time.
5. Check if b is in the new string. If yes, return q + 1.
6. Return -1 otherwise.

C++ Code

#include <string>

using namespace std;

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        int m = a.length();
        int n = b.length();
        
        // Calculate the minimum number of repeats mathematically
        int min_repeats = n / m;
        if (n % m != 0) {
            min_repeats++;
        }
        
        string repeated_a = "";
        
        // Pre-allocate memory to avoid multiple reallocations
        repeated_a.reserve((min_repeats + 1) * m);
        
        // Build the base repeated string
        for (int i = 0; i < min_repeats; i++) {
            repeated_a += a;
        }
        
        // First check (q repetitions)
        if (repeated_a.find(b) != string::npos) {
            return min_repeats;
        }
        
        // Second check (q + 1 repetitions)
        repeated_a += a;
        if (repeated_a.find(b) != string::npos) {
            return min_repeats + 1;
        }
        
        return -1;
    }
};

Dry Run

Approach 3: KMP String Matching

Intuition

If the interviewer wants a strict $O(N + M)$ guaranteed worst-case time complexity, the built-in find() won't cut it. You must implement a linear-time Pattern Matching algorithm. The Knuth-Morris-Pratt (KMP) algorithm is the gold standard here.

KMP works by pre-processing the target string (b) to create an LPS (Longest Proper Prefix which is also Suffix) array. This array tells the algorithm how far to backtrack when a character mismatch occurs, completely eliminating the need to re-evaluate characters we've already matched.

Algorithm

1. LPS Array Construction: Create an array of size b.length(). Keep two pointers. If characters match, increment both and store the length in the array. If they mismatch, use previously computed LPS values to backtrack without resetting completely.
2. Setup KMP Search: Build the repeated_a string up to q + 1 repetitions just like in Approach 2.
3. Pattern Searching: Iterate through repeated_a. If characters match with b, advance both pointers. If a full match is found, check if the match occurred within q repetitions or q + 1 repetitions. If a mismatch occurs, use the LPS array to slide the pattern b efficiently instead of going back to the beginning.

C++ Code

#include <string>
#include <vector>

using namespace std;

class Solution {
private:
    // Helper function to build the LPS (Longest Prefix Suffix) array
    vector<int> computeLPS(const string& pattern) {
        int m = pattern.length();
        vector<int> lps(m, 0);
        int len = 0; // Length of the previous longest prefix suffix
        int i = 1;
        
        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    // Backtrack to the previous longest prefix suffix
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // KMP Search function
    bool KMPSearch(const string& text, const string& pattern) {
        int n = text.length();
        int m = pattern.length();
        
        if (m == 0) return true;
        
        vector<int> lps = computeLPS(pattern);
        int i = 0; // index for text
        int j = 0; // index for pattern
        
        while (i < n) {
            if (pattern[j] == text[i]) {
                j++;
                i++;
            }
            if (j == m) {
                return true; // Match found
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1]; // Use LPS array to skip characters
                } else {
                    i++;
                }
            }
        }
        return false;
    }

public:
    int repeatedStringMatch(string a, string b) {
        int m = a.length();
        int n = b.length();
        
        int min_repeats = n / m;
        if (n % m != 0) min_repeats++;
        
        string repeated_a = "";
        repeated_a.reserve((min_repeats + 1) * m);
        
        for (int i = 0; i < min_repeats; i++) {
            repeated_a += a;
        }
        
        if (KMPSearch(repeated_a, b)) return min_repeats;
        
        repeated_a += a;
        if (KMPSearch(repeated_a, b)) return min_repeats + 1;
        
        return -1;
    }
};

Dry Run

Complexity Analysis

• Time Complexity: $O(N + M)$. Generating the LPS array takes $O(M)$. The KMP search traverses the text string once, taking $O(N + M)$ time. This is a strict worst-case guarantee.
• Space Complexity: $O(N + M)$. We still build repeated_a, and we use an additional $O(M)$ space for the LPS array.

Advantages

• Guaranteed linear time limit. No malicious test case can cause a Time Limit Exceeded.
• Shows deep computer science knowledge.

Disadvantages

• High complexity to write out by hand.
• Prone to off-by-one errors during the LPS generation loop if not practiced well.

Approach 4: Rolling Hash (Rabin-Karp)

Intuition

Instead of comparing characters one by one, Rabin-Karp converts every string into a numerical hash value.

First, compute the hash of the pattern b.

Then repeatedly concatenate a until its length is sufficient (up to q + 1 repetitions). Rather than checking every substring character-by-character, slide a window of length b.length() across the repeated string while maintaining a rolling hash.

If the window's hash matches the pattern's hash, perform one final character-by-character verification to avoid false positives caused by hash collisions.

Because updating the hash after sliding the window takes O(1) time, the algorithm is much faster than naive substring matching on average.

Algorithm

1. Compute the minimum repetitions q.
2. Build the repeated string up to q + 1 repetitions.
3. Compute the hash of pattern b.
4. Compute the hash of the first window of the repeated string.
5. Compare both hashes.
6. If they match, verify characters.
7. Otherwise, slide the window one character forward and update the hash in O(1).
8. If a match is found, return the required repetitions.
9. Otherwise return -1.

C++ Code

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    int repeatedStringMatch(string a, string b) {

        int m = a.length();
        int n = b.length();

        int repeat = (n + m - 1) / m;

        string repeated = "";

        while (repeat--) {
            repeated += a;
        }

        if (containsRK(repeated, b))
            return (n + m - 1) / m;

        repeated += a;

        if (containsRK(repeated, b))
            return (n + m - 1) / m + 1;

        return -1;
    }

private:

    bool containsRK(string text, string pattern) {

        const long long BASE = 256;
        const long long MOD = 1000000007;

        int n = text.length();
        int m = pattern.length();

        if (m > n)
            return false;

        long long patternHash = 0;
        long long windowHash = 0;
        long long power = 1;

        for (int i = 0; i < m - 1; i++)
            power = (power * BASE) % MOD;

        for (int i = 0; i < m; i++) {
            patternHash = (patternHash * BASE + pattern[i]) % MOD;
            windowHash = (windowHash * BASE + text[i]) % MOD;
        }

        for (int i = 0; i <= n - m; i++) {

            if (patternHash == windowHash) {

                if (text.substr(i, m) == pattern)
                    return true;
            }

            if (i < n - m) {

                windowHash =
                    (windowHash - text[i] * power % MOD + MOD) % MOD;

                windowHash =
                    (windowHash * BASE + text[i + m]) % MOD;
            }
        }

        return false;
    }
};

Dry Run

Complexity Analysis

Advantages

• Average-case linear performance.
• Efficient rolling hash updates in O(1).
• Much faster than naive matching for large inputs.
• Widely used in plagiarism detection, DNA matching, and document search.

Disadvantages

• Hash collisions are possible, so character verification is still required.
• Worst-case complexity can degrade to O(N × M).
• More difficult to implement than std::string::find().
• For this problem, KMP provides a strict linear-time guarantee, making it a better interview choice.

Common Mistakes

• Missing the q + 1 check: Many candidates correctly identify q = ceil(b.len / a.len), but forget that if b starts at the very last character of a, it will spill over into an extra repetition block. Always check q + 1.
• Checking q + 2 or more: Appending a more than q+1 times is a waste of compute cycles. If it hasn't matched by q+1 times, it never will.
• Using floor instead of integer math tricks: Using floats like ceil(double(n)/m) can sometimes introduce subtle floating-point inaccuracies or slow down execution. Using n / m and adding 1 if n % m != 0 is the standard, safe C++ approach.

Interview Tips

• Communicate the bounds first: Start your interview by explaining why you only need to check q and q + 1 iterations. Drawing a bounding box on the whiteboard (or virtual pad) proves you understand the math, which is half the battle.
• Don't jump straight to KMP: Start by writing Approach 2 (std::string::find()). Explain to the interviewer that standard library functions are heavily optimized and usually sufficient.
• Be prepared for the follow-up: If the interviewer asks, "How would you optimize this if standard library functions were banned, or if the string consisted of highly repetitive malicious characters?" That is your cue to mention and implement the KMP algorithm.

FAQs

Why only check repeatCount + 1? Because b must start somewhere within the first copy of a to be a valid substring. The maximum length b can extend into is b.length(). Therefore, a.length() (the first copy) + b.length() is the absolute maximum span, which is covered exactly by q + 1 repetitions.

Can KMP improve performance in everyday applications? Yes, but often modern languages implement highly sophisticated find() functions (like Two-Way string matching in glibc) that handle standard inputs extremely well. KMP shines brightest when dealing with massive datasets containing highly repetitive patterns, such as DNA sequences.

Why doesn't the brute force approach always pass? In platforms like LeetCode, test cases are designed to push time limits. A brute force approach might perform unnecessary find() operations on partially built strings, doing redundant work that eventually leads to a Time Limit Exceeded error.

code link :

https://leetcode.com/problems/repeated-string-match/description/

video link:

Rabin karp reference