LeetCode 686: Repeated String Match Solution in Python – A Step-by-Step Guide

What Is LeetCode 686: Repeated String Match?

In LeetCode 686: Repeated String Match, you’re given two strings a and b, and your task is to find the minimum number of times a must be repeated so that b becomes a substring of the resulting string. Return this integer, or -1 if it’s impossible. For example, with a = "abcd" and b = "cdabcdab", repeating a three times ("abcdabcdabcd") contains b, so return 3. With a = "aa" and b = "a", one repetition ("aa") works, so return 1. The problem tests your ability to handle string repetition and substring matching efficiently.

Problem Statement

• Input:
• a: String to repeat.
• b: Target substring.
• Output: An integer—minimum repetitions of a to contain b, or -1 if impossible.
• Rules:
• Repeat a some number of times.
• Check if b is a substring of the result.
• Return smallest such number or -1.

Constraints

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

Examples

• Input: a = "abcd", b = "cdabcdab"
• Output: 3 ("abcdabcdabcd" contains "cdabcdab")
• Input: a = "a", b = "aa"
• Output: 2 ("aa" contains "aa")
• Input: a = "a", b = "b"
• Output: -1 (No repetition of "a" contains "b")
• Input: a = "abc", b = "wxyz"
• Output: -1 (No match possible)

These examples set the strings—let’s solve it!

Understanding the Problem: Repeating for a Match

To solve LeetCode 686: Repeated String Match in Python, we need to find the smallest integer k such that repeating string ak times contains b as a substring, or determine it’s impossible. A brute-force approach—repeating a indefinitely and checking each time—would be inefficient for large lengths (≤ 10⁴). Since we’re looking for a substring match with repetition, we can optimize by estimating the minimum repetitions needed and checking a bounded range, or use advanced string matching like KMP. We’ll use:

• Best Solution (String Concatenation with Boundary Check): O(n + m) time, O(n + m) space—fast and practical.
• Alternative Solution (KMP Algorithm): O(n + m) time, O(m) space—precise but complex.

Let’s start with the concatenation solution, breaking it down for beginners.

Best Solution: String Concatenation with Boundary Check

Why This Is the Best Solution

The string concatenation with boundary check approach is the top choice for LeetCode 686 because it’s efficient—O(n + m) time with O(n + m) space, where n = len(a) and m = len(b)—and uses a clever insight: the minimum repetitions needed is bounded by ceil(len(b) / len(a)), plus one extra to handle edge cases, making it simple and practical. It fits constraints (n, m ≤ 10⁴) perfectly and is intuitive once you see the boundary logic. It’s like repeating a just enough times to catch b and checking if it fits!

How It Works

Think of this as a string stretcher:

• Step 1: Calculate Minimum Repetitions:
• Min k ≈ ceil(len(b) / len(a)).
• Step 2: Build Repeated String:
• Concatenate a for k times, then k+1 times.
• Step 3: Check Substring:
• If b in a k or a (k + 1), return k or k + 1.
• Else, return -1.
• Step 4: Return Result:
• Smallest k or -1 if no match.

It’s like a fit finder—stretch and check!

Step-by-Step Example

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

• Step 1: Calculate:
• len(a) = 4, len(b) = 8.
• Min k = ceil(8 / 4) = 2.
• Step 2: Build:
• k = 2: "abcdabcd" (8 chars).
• k + 1 = 3: "abcdabcdabcd" (12 chars).
• Step 3: Check:
• "abcdabcd": "cdabcdab" not found (8 < 8, needs more).
• "abcdabcdabcd": "cdabcdab" found at index 2.
• Return 3.
• Step 4: Return 3.
• Output: 3.

Example: a = "a", b = "b"

• Step 1: k = ceil(1 / 1) = 1.
• Step 2: "a", "aa".
• Step 3: "b" not in "a" or "aa", return -1.
• Output: -1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        # Step 1: Calculate minimum repetitions
        n, m = len(a), len(b)
        k = (m + n - 1) // n  # ceil(m / n)

        # Step 2: Build repeated strings
        repeated = a * k
        if b in repeated:
            return k

        # Step 3: Check one more repetition
        repeated += a
        if b in repeated:
            return k + 1

        # Step 4: Return -1 if no match
        return -1

• Lines 4-5: Calculate: k = ceil(m /

n) using integer division trick.

• Lines 8-10: Check k: Build a * k, return k if b found.
• Lines 13-15: Check k+1: Add one more a, return k+1 if found.
• Line 18: Return -1 if no match.
• Time Complexity: O(n + m)—string construction and substring check.
• Space Complexity: O(n + m)—repeated string storage.

This is like a string tailor—fit and measure!

Alternative Solution: KMP Algorithm

Why an Alternative Approach?

The KMP (Knuth-Morris-Pratt) algorithm approach uses pattern matching—O(n + m) time, O(m) space. It’s more sophisticated, building a prefix table to efficiently search for b in repeated a, but overcomplicates this problem since simple concatenation suffices. It’s like using a precision tool when a quick stitch works!

How It Works

Picture this as a pattern matcher:

• Step 1: Build KMP prefix table for b.
• Step 2: Simulate repetition:
• Search b in a + a + ..., stop when match found or impossible.
• Step 3: Calculate repetitions:
• Use match position and lengths to find k.
• Step 4: Return result.

It’s like a string scanner—pattern and count!

Step-by-Step Example

Example: Same as above

• Step 1: Prefix table for "cdabcdab":
• lps = [0, 0, 0, 0, 1, 2, 3, 0].
• Step 2: Search in "abcdabcdabcd":
• Match at index 2 after 3 reps, k = 3.
• Step 3: Return 3.
• Output: 3.

Code for KMP Approach

Copy codeclass Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        # Step 1: Build KMP prefix table
        def build_lps(pattern: str) -> List[int]:
            lps = [0] * len(pattern)
            length = 0
            i = 1
            while i < len(pattern):
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                elif length > 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
            return lps

        # Step 2: KMP search simulation
        n, m = len(a), len(b)
        lps = build_lps(b)
        k = (m + n - 1) // n  # Min repetitions

        # Check k and k+1 repetitions
        text = a * k
        if self.kmp_search(text, b, lps):
            return k
        text += a
        if self.kmp_search(text, b, lps):
            return k + 1
        return -1

    def kmp_search(self, text: str, pattern: str, lps: List[int]) -> bool:
        i = j = 0
        while i < len(text):
            if text[i] == pattern[j]:
                i += 1
                j += 1
            if j == len(pattern):
                return True
            elif i < len(text) and text[i] != pattern[j]:
                if j > 0:
                    j = lps[j - 1]
                else:
                    i += 1
        return False

• Lines 4-18: build_lps: KMP prefix table.
• Lines 21-30: Main: Calculate k, check k and k+1 reps.
• Lines 33-46: kmp_search: Search with KMP, return True if match.
• Time Complexity: O(n + m)—KMP matching.
• Space Complexity: O(m)—lps array.

It’s a pattern prober—scan and fit!

Comparing the Two Solutions

• Concatenation (Best):
• Pros: O(n + m) time, O(n + m) space, simple and fast.
• Cons: Slightly more space.
• KMP (Alternative):
• Pros: O(n + m) time, O(m) space, precise matching.
• Cons: More complex, unnecessary overhead.

Concatenation wins for simplicity.

Additional Examples and Edge Cases

• Input: a = "aa", b = "a"
• Output: 1.
• Input: a = "abc", b = "xyz"
• Output: -1.

Concatenation handles these well.

Complexity Breakdown

• Concatenation: Time O(n + m), Space O(n + m).
• KMP: Time O(n + m), Space O(m).

Concatenation is optimal for ease.

Key Takeaways

• Concatenation: String stretching—smart!
• KMP: Pattern matching—clear!
• Matches: Weaving is fun.
• Python Tip: Strings rock—see Python Basics.

Final Thoughts: Weave That Match

LeetCode 686: Repeated String Match in Python is a fun string challenge. String concatenation with boundary check offers simplicity and speed, while KMP provides a precise alternative. Want more? Try LeetCode 28: Find the Index of the First Occurrence in a String or LeetCode 459: Repeated Substring Pattern. Ready to repeat? Head to Solve LeetCode 686 on LeetCode and find that match today!