LeetCode 459: Repeated Substring Pattern Solution in Python – A Step-by-Step Guide

What Is LeetCode 459: Repeated Substring Pattern?

In LeetCode 459: Repeated Substring Pattern, you’re given a string s, and your task is to determine if it can be constructed by repeating a substring multiple times. For example, "abab" is "ab" repeated twice, and "abcabcabc" is "abc" three times, so both return True, but "aba" doesn’t fit the mold. It’s like checking if a string is a chorus of a smaller tune played over and over.

Problem Statement

• Input: s (str)—input string.
• Output: bool—True if s is a repeated substring pattern, False otherwise.
• Rules:
• s must be formed by repeating a substring k times (k > 1).
• Substring length must divide s.length evenly.

Constraints

• 1 <= s.length <= 10^4.
• s consists of lowercase English letters.

Examples to Get Us Started

• Input: s = "abab"
• Output: True ("ab" repeated 2 times).
• Input: s = "aba"
• Output: False (No repeating substring).
• Input: s = "abcabcabcabc"
• Output: True ("abc" repeated 4 times).

Understanding the Problem: Spotting the Repetition

To solve LeetCode 459: Repeated Substring Pattern in Python, we need to check if s is a concatenation of some substring repeated k times (k > 1). A naive approach—testing every possible substring—works but could be O(n²). The key insight? A repeated pattern has a clever property we can exploit with string manipulation or divisibility checks. We’ll explore:

• Best Solution (String Concatenation Trick): O(n) time, O(n) space—fast and genius.
• Alternative Solution (Brute Force Substring Check): O(n²) time, O(1) space—simple but slower.

Let’s dive into the concatenation trick—it’s the detective’s magnifying glass we need.

Best Solution: String Concatenation Trick with Substring Check

Why This Is the Best Solution

The string concatenation trick is the top pick because it’s O(n) time and O(n) space, using a brilliant property: if s is a repeated substring, then s + s (doubled) contains s starting at any position except the ends, specifically at index 1 after removing the first and last characters. It’s like doubling a song and checking if the original tune plays clearly within the echo—ingenious and quick!

How It Works

Here’s the strategy:

• Step 1: Create double = s + s.
• Step 2: Remove first and last characters: double[1:-1].
• Step 3: Check if s is in double[1:-1] using string search.
• Step 4: Return True if found, False otherwise.
• Why It Works:
• If s = "ab" * 2 = "abab", then s + s = "abababab".
• double[1:-1] = "bababa", contains "abab" at index 0.
• Non-repeated (e.g., "aba") fails this check.

Step-by-Step Example

Example: s = "abab"

• Double: "abab" + "abab" = "abababab".
• Trim: "abababab"[1:-1] = "bababa".
• Check: "abab" in "bababa" → True (starts at 0).
• Result: True.

Example: s = "aba"

• Double: "abaaba".
• Trim: "baab".
• Check: "aba" not in "baab" → False.
• Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        # Step 1: Double the string
        double = s + s

        # Step 2: Remove first and last characters
        trimmed = double[1:-1]

        # Step 3: Check if s is in trimmed
        return s in trimmed

• Line 4: Concatenate s with itself (e.g., "abab" → "abababab").
• Line 7: Slice off first and last chars (e.g., "bababa").
• Line 10: Use Python’s in to check substring presence.
• Time Complexity: O(n)—string search (KMP-like internally).
• Space Complexity: O(n)—double string.

It’s like a string-pattern X-ray!

Why It Works (Deep Dive)

• If s = p * k (p repeated k times):
• s + s = p * k + p * k = p * (2k).
• double[1:-1] = p[1:] + p * (2k-2) + p[:-1].
• Contains p * k = s if k ≥ 2.
• If not repeated, no full s appears in trimmed.

Alternative Solution: Brute Force Substring Iteration

Why an Alternative Approach?

The brute force method checks all possible substring lengths—O(n²) time, O(1) space—testing if s is a repetition of each. It’s slower but intuitive, like trying every puzzle piece to see if it fits the whole picture. Good for small strings or clarity!

How It Works

• Step 1: Iterate substring lengths from 1 to n//2.
• Step 2: For each length l, check if s == substring * (n//l).
• Step 3: Return True if match found, False otherwise.

Step-by-Step Example

Example: s = "abab"

• n = 4:
• Len 1: "a" * 4 = "aaaa" ≠ "abab".
• Len 2: "ab" * 2 = "abab" == "abab", True.
• Result: True.

Example: s = "aba"

• Len 1: "a" * 3 ≠ "aba".
• Len 1.5: Invalid.
• Result: False.

Code for Brute Force

Copy codeclass Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)

        # Check all possible substring lengths
        for length in range(1, n // 2 + 1):
            if n % length == 0:  # Must divide evenly
                substring = s[:length]
                if substring * (n // length) == s:
                    return True
        return False

• Line 4-9: Loop lengths, check if substring repeats to form s.
• Time Complexity: O(n²)—string multiplication and comparison.
• Space Complexity: O(1)—minimal extra space.

It’s a slow pattern prober!

Comparing the Two Solutions

• Concatenation Trick (Best):
• Pros: O(n), fast, clever.
• Cons: O(n) space.
• Brute Force (Alternative):
• Pros: O(n²), simple, O(1) space.
• Cons: Slower.

Concatenation wins for speed.

Edge Cases and More Examples

• Input: "a" → False.
• Input: "aa" → True.
• Input: "abcd" → False.

Concatenation handles all perfectly.

Complexity Recap

• Concatenation: Time O(n), Space O(n).
• Brute Force: Time O(n²), Space O(1).

Concatenation’s the champ.

Key Takeaways

• Concatenation: String trick magic.
• Brute Force: Check every piece.
• Python Tip: Strings hide patterns—see [Python Basics](/python/basics).

Final Thoughts: Crack That Pattern

LeetCode 459: Repeated Substring Pattern in Python is a string-sleuthing delight. The concatenation trick is your fast detective tool, while brute force is a steady search. Want more string challenges? Try LeetCode 3: Longest Substring Without Repeating Characters or LeetCode 28: Implement strStr(). Ready to spot some repeats? Head to Solve LeetCode 459 on LeetCode and unravel the mystery today—your coding skills are pattern-ready!