Repeated String Match

Medium

💭 Introduction

You’re given two strings a and b. Your task is to find the minimum number of times you need to repeat string a so that string b becomes a substring of the repeated string.

If it’s impossible to make b a substring of repeated a, return -1.

For example:

• a = "abcd", b = "cdabcdab"
• Repeat a three times: "abcdabcdabcd"
• Now b is a substring! Answer: 3

Your goal is to find this minimum number of repetitions.

🧩 Problem Statement

LeetCode #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.

🔍 Example 1:

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

Explanation:

We repeat a three times: "abcdabcdabcd". Now b = "cdabcdab" is a substring.

🔍 Example 2:

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

Explanation:

We repeat a twice: "aa". Now b = "aa" is a substring.

🔍 Example 3:

Input: a = "a", b = "a"
Output: 1

Explanation:

b is already a substring of a.

🔍 Example 4:

Input: a = "abc", b = "wxyz"
Output: -1

Explanation:

No matter how many times we repeat a, b will never be a substring because a doesn’t contain the characters in b.

🧠 Step 1: Understanding the Problem

Let’s break down what we’re really asking:

Key Observations:

1. Minimum repetitions needed:
   • At minimum, we need ceil(len(b) / len(a)) repetitions
   • Why? Because the repeated string must be at least as long as b
2. Maximum repetitions to check:
   • We never need more than ceil(len(b) / len(a)) + 2 repetitions
   • Why? If b isn’t found by then, it never will be
3. Why +2?
   • b might start near the end of one repetition and end in the next
   • Example: a = "abc", b = "cabca"
   • Need: "abcabcabc" (3 times, where ceil(5/3) + 2 = 3)

Visual Example:

a = "abc"
b = "cabca"

Repetition 1: "abc"
Repetition 2: "abc|abc"     ← b starts here
Repetition 3: "abc|abc|abc" ← b ends here
              "  cabca  "

🤔 Step 2: The Naive Approach

Simply repeat a and check if b is a substring:

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        # Calculate minimum and maximum repetitions
        min_reps = -(-len(b) // len(a))  # Ceiling division
        max_reps = min_reps + 2
        
        # Try each number of repetitions
        for count in range(min_reps, max_reps + 1):
            repeated = a * count
            if b in repeated:
                return count
        
        return -1

How it works:

1. Calculate minimum repetitions needed
2. Try up to 2 more repetitions
3. Check if b is substring using Python’s in operator

⏱️ Time Complexity: $O(n \times m)$ where n = len(repeated string), m = len(b)

📦 Space Complexity: $O(n)$ for the repeated string

🚀 Step 3: Optimized Approach with Early Termination

We can optimize by checking character existence first:

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        # Early termination: if b has chars not in a, impossible
        if not set(b).issubset(set(a)):
            return -1
        
        # Calculate repetitions needed
        min_reps = -(-len(b) // len(a))  # Ceiling division
        
        # Try minimum repetitions
        repeated = a * min_reps
        if b in repeated:
            return min_reps
        
        # Try one more repetition
        repeated += a
        if b in repeated:
            return min_reps + 1
        
        # Try one more (edge case where b spans multiple repetitions)
        repeated += a
        if b in repeated:
            return min_reps + 2
        
        return -1

Improvements:

1. Early termination: Check if all characters in b exist in a
2. Incremental checking: Build string incrementally instead of trying all at once
3. Clear logic: Explicitly check min, min+1, and min+2 repetitions

⏱️ Time Complexity: $O(n \times m)$ where n = len(repeated string), m = len(b)

📦 Space Complexity: $O(n)$

⚙️ Step 4: Using KMP Algorithm (Advanced)

For very large strings, we can use the KMP (Knuth-Morris-Pratt) pattern matching algorithm:

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        # Early termination
        if not set(b).issubset(set(a)):
            return -1
        
        def kmp_search(text, pattern):
            """KMP pattern matching algorithm"""
            # Build LPS (Longest Prefix Suffix) array
            def build_lps(pattern):
                lps = [0] * len(pattern)
                length = 0
                i = 1
                
                while i < len(pattern):
                    if pattern[i] == pattern[length]:
                        length += 1
                        lps[i] = length
                        i += 1
                    else:
                        if length != 0:
                            length = lps[length - 1]
                        else:
                            lps[i] = 0
                            i += 1
                return lps
            
            lps = build_lps(pattern)
            i = j = 0
            
            while i < len(text):
                if pattern[j] == text[i]:
                    i += 1
                    j += 1
                
                if j == len(pattern):
                    return True
                elif i < len(text) and pattern[j] != text[i]:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return False
        
        # Calculate repetitions
        min_reps = -(-len(b) // len(a))
        
        for count in range(min_reps, min_reps + 3):
            repeated = a * count
            if kmp_search(repeated, b):
                return count
        
        return -1

Why KMP?

• Python’s in operator uses a simple algorithm
• For very large strings, KMP is more efficient
• KMP has $O(n + m)$ time complexity for pattern matching

⏱️ Time Complexity: $O(n + m)$ for KMP search

📦 Space Complexity: $O(n + m)$

🎯 Step 5: Mathematical Approach

We can calculate the exact range without building the full string:

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        # Early termination
        if not set(b).issubset(set(a)):
            return -1
        
        len_a, len_b = len(a), len(b)
        
        # Minimum repetitions needed
        min_reps = (len_b + len_a - 1) // len_a  # Ceiling division
        
        # Check min_reps and min_reps + 1
        for count in [min_reps, min_reps + 1]:
            repeated = a * count
            if b in repeated:
                return count
        
        return -1

Why only check min_reps and min_reps + 1?

Actually, we might need min_reps + 2 in rare cases. Here’s the corrected version:

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        # Early termination
        if not set(b).issubset(set(a)):
            return -1
        
        # Calculate minimum repetitions
        min_reps = -(-len(b) // len(a))  # Ceiling division
        
        # Check min_reps, min_reps + 1, and min_reps + 2
        for count in range(min_reps, min_reps + 3):
            if b in a * count:
                return count
        
        return -1

🎯 Key Insights

1. Character check first: If b contains characters not in a, return -1 immediately

2. Minimum repetitions: At least ceil(len(b) / len(a)) repetitions needed

3. Maximum to check: Never need more than min_reps + 2 repetitions

4. Why +2?: b might start near the end of one cycle and span into the next

5. Edge cases: Handle when len(a) > len(b) or when strings are equal

📊 Complexity Summary

Approach	Time	Space	Notes
Naive	$O(n \times m)$	$O(n)$	Simple, works well
With Early Check	$O(n \times m)$	$O(n)$	Faster in practice
KMP Algorithm	$O(n + m)$	$O(n + m)$	Best for large strings
Mathematical	$O(n \times m)$	$O(n)$	Clean and efficient

Where n = length of repeated string, m = length of b

🌟 Edge Cases to Consider

1. Empty strings: a = "" or b = "" → Handle appropriately
2. b longer than a: a = "ab", b = "ababab" → Need multiple repetitions
3. b equals a: a = "abc", b = "abc" → Return 1
4. Impossible case: a = "abc", b = "xyz" → Return -1
5. Single character: a = "a", b = "aa" → Return 2
6. b spans boundaries: a = "abc", b = "cabca" → Needs careful handling

💡 Common Mistakes

1. Not checking character existence: Waste time building strings when impossible
2. Wrong repetition count: Forgetting the +2 buffer for boundary cases
3. Integer overflow: In other languages, be careful with large repetitions
4. Not handling empty strings: Edge case that needs special handling
5. Building too many repetitions: Inefficient memory usage

🧪 Step-by-Step Example

Let’s trace through a = "abcd", b = "cdabcdab":

Step 1: Check characters
- set(b) = {'c', 'd', 'a', 'b'}
- set(a) = {'a', 'b', 'c', 'd'}
- All chars in b exist in a ✓

Step 2: Calculate minimum repetitions
- len(b) = 8, len(a) = 4
- min_reps = ceil(8/4) = 2

Step 3: Try min_reps = 2
- repeated = "abcdabcd"
- Is "cdabcdab" in "abcdabcd"? NO

Step 4: Try min_reps + 1 = 3
- repeated = "abcdabcdabcd"
- Is "cdabcdab" in "abcdabcdabcd"? YES ✓
         "  cdabcdab  "

Answer: 3

🔍 Variations of This Problem

1. Repeated Substring Pattern — Check if string can be formed by repeating a substring
2. Rotate String — Check if one string is rotation of another
3. Implement strStr() — Find first occurrence of substring
4. String Matching with Wildcards — Pattern matching with special characters

💡 Related Problems

• KMP Algorithm - Efficient pattern matching
• Implement strStr() - Substring search
• Rotate String - Similar string manipulation
• Repeated Substring Pattern - Related repetition problem

🏆 Why This Problem Matters

1. String manipulation: Tests understanding of string operations
2. Pattern matching: Foundation for more complex algorithms
3. Optimization thinking: Multiple approaches from naive to optimal
4. Edge case handling: Many corner cases to consider
5. Real-world applications: Text processing, DNA sequencing, data compression

🎓 Key Takeaways

• Early termination: Check character existence before building strings
• Mathematical bounds: Calculate exact range of repetitions to check
• Space efficiency: Don’t build more repetitions than necessary
• Pattern matching: Can use KMP for very large strings
• Edge cases matter: Handle boundary conditions carefully

📝 Interview Tips

1. Start with character check: Show you’re thinking about optimization
2. Explain the math: Why min_reps and why +2?
3. Discuss trade-offs: Naive vs KMP approach
4. Test edge cases: Empty strings, equal strings, impossible cases
5. Code cleanly: Use clear variable names and comments