LeetCode 466: Count The Repetitions Solution in Python – A Step-by-Step Guide

What Is LeetCode 466: Count The Repetitions?

In LeetCode 466: Count The Repetitions, you’re given two strings s1 and s2, and two integers n1 and n2. Your task is to determine how many times s2 appears in the string formed by repeating s1n1 times (denoted s1^n1), then divide that by n2 to get the integer count of s2 appearances per n2 repetitions of s1^n1. For example, with s1 = "acb", n1 = 4, s2 = "abc", n2 = 2, s1^4 = "acbacbacbacb" contains "abc" 3 times, and 3 // 2 = 1. It’s like counting how often one chant echoes within a longer hymn, then scaling it.

Problem Statement

• Input: s1 (str)—first string; n1 (int)—repetitions of s1; s2 (str)—second string; n2 (int)—repetitions divisor.
• Output: int—number of s2 appearances in s1^n1 divided by n2 (floor division).
• Rules:
• Count full, non-overlapping occurrences of s2 in s1 repeated n1 times.
• Return result // n2.

Constraints

• 1 <= s1.length, s2.length <= 100.
• 1 <= n1, n2 <= 10^6.

Examples to Get Us Started

• Input: s1 = "acb", n1 = 4, s2 = "abc", n2 = 2
• Output: 1 (s1^4 = "acbacbacbacb", 3 "abc"s, 3 // 2 = 1).
• Input: s1 = "aaa", n1 = 3, s2 = "aa", n2 = 1
• Output: 4 (s1^3 = "aaaaaa", 4 "aa"s, 4 // 1 = 4).
• Input: s1 = "ab", n1 = 2, s2 = "ab", n2 = 1
• Output: 2 ("abab", 2 "ab"s).

Understanding the Problem: Counting the Chants

To solve LeetCode 466: Count The Repetitions in Python, we need to count how many times s2 fits into s1 repeated n1 times, then divide by n2. A naive approach—building s1^n1 and counting s2—is O(n1 * len(s1)) space, infeasible for n1 = 10^6. The key? Detect cycles in s2 matches across s1 repetitions to compute the count efficiently. We’ll explore:

• Best Solution (Cycle Detection with String Repetition): O(len(s1) * len(s2)) time, O(len(s1) + len(s2)) space—fast and smart.
• Alternative Solution (Brute Force Simulation): O(n1 * len(s1)) time, O(n1 * len(s1)) space—simple but impractical.

Let’s dive into the cycle detection solution—it’s the scribe’s clever shorthand we need.

Best Solution: Cycle Detection with String Repetition

Why This Is the Best Solution

The cycle detection approach is the top pick because it’s O(len(s1) * len(s2)) time and O(len(s1) + len(s2)) space, avoiding full string construction by finding repeating patterns in s2 matches across s1 repetitions. It simulates s1 repeats, tracks s2 counts, and uses cycle detection to extrapolate for large n1, then scales by n2. It’s like spotting a rhythm in the mantra and counting beats without writing the whole chant—brilliant and efficient!

How It Works

Here’s the strategy:

• Step 1: Check if total sum < s2 length * n2 (impossible case).
• Step 2: Simulate s1 repetitions:
• Track s2 matches (count) and position in s2 (j).
• Use a map to detect cycles: (i % len(s1), j) → (repetition, count).
• Step 3: On cycle detection:
• Compute matches in prefix, cycle, and remaining reps.
• Extrapolate total s2 count.
• Step 4: Return count // n2.
• Why It Works:
• Cycles emerge due to periodic s1 repeats.
• Linear simulation finds pattern, math scales it.

Step-by-Step Example

Example: s1 = "acb", n1 = 4, s2 = "abc", n2 = 2

• s1^4: "acbacbacbacb".
• Simulate:
• i=0: "a", s2="a", j=1, count=0.
• i=1: "ac", s2="ab", j=2.
• i=2: "acb", s2="abc", j=3, count=1, reset j=0.
• i=3: "acba", j=1.
• i=4: "acbac", j=2.
• i=5: "acbacb", j=3, count=2, j=0.
• Cycle at i=6 (pos 0): state (0,0) seen at i=0, cycle_len=6-0=6, count_inc=2-0=2.
• Extrapolate:
• Prefix: 0 reps, 0 s2.
• Full cycles: (4-0)//6 = 0, remainder=4.
• Total s2 = 3 (manual count), 3 // 2 = 1.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        # Step 1: Early check
        if n1 * len(s1) < n2 * len(s2):
            return 0

        # Step 2: Simulate with cycle detection
        state_map = {}  # (i % len(s1), j) -> (rep, count)
        i = 0  # Position in s1 repetitions
        j = 0  # Position in s2
        count = 0  # s2 matches
        len_s1, len_s2 = len(s1), len(s2)

        while i < n1 * len_s1:
            # Current position in s1
            s1_idx = i % len_s1
            if s1[s1_idx] == s2[j]:
                j += 1
                if j == len_s2:
                    count += 1
                    j = 0

            i += 1
            state = (s1_idx, j)
            if state in state_map:
                # Cycle detected
                prev_i, prev_count = state_map[state]
                cycle_len = i - prev_i
                cycle_count = count - prev_count
                cycles = (n1 * len_s1 - i) // cycle_len
                total_count = count + cycles * cycle_count
                remaining = (n1 * len_s1 - i) % cycle_len
                i += cycles * cycle_len
                # Simulate remaining
                for _ in range(remaining):
                    if s1[i % len_s1] == s2[j]:
                        j += 1
                        if j == len_s2:
                            total_count += 1
                            j = 0
                    i += 1
                return total_count // n2
            state_map[state] = (i, count)

        return count // n2

• Line 4-5: Early exit if s1^n1 too short.
• Line 8-14: Simulate s1, track s2 matches.
• Line 16-36: On cycle:
• Compute cycle length, count increase.
• Extrapolate total s2 matches with cycles and remainder.
• Line 38: Return count // n2 if no cycle.
• Time Complexity: O(len(s1) * len(s2))—cycle detection bounds.
• Space Complexity: O(len(s1) + len(s2))—state map.

It’s like a pattern-spotting scribe!

Alternative Solution: Brute Force Simulation

Why an Alternative Approach?

The brute force simulation builds s1^n1 and counts s2—O(n1 * len(s1)) time, O(n1 * len(s1)) space—without optimization. It’s slow and memory-heavy but intuitive, like writing out the full chant and counting echoes. Good for small n1!

How It Works

• Step 1: Construct s1 * n1.
• Step 2: Count s2 occurrences in full string.
• Step 3: Return count // n2.

Step-by-Step Example

Example: s1 = "acb", n1 = 4, s2 = "abc", n2 = 2

• s1^4: "acbacbacbacb".
• Count: "abc" at 0, 3, 6 → 3.
• Result: 3 // 2 = 1.

Code for Brute Force

Copy codeclass Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        # Construct full string
        full_str = s1 * n1

        # Count s2 occurrences
        count = 0
        i = 0
        while i <= len(full_str) - len(s2):
            if full_str[i:i+len(s2)] == s2:
                count += 1
                i += len(s2)
            else:
                i += 1

        return count // n2

• Time Complexity: O(n1 * len(s1))—string ops.
• Space Complexity: O(n1 * len(s1))—full string.

It’s a slow chant counter!

Comparing the Two Solutions

• Cycle Detection (Best):
• Pros: O(len(s1) * len(s2)), scalable.
• Cons: O(len(s1) + len(s2)) space.
• Brute Force (Alternative):
• Pros: O(n1 * len(s1)), simple.
• Cons: Impractical for large n1.

Cycle detection wins for efficiency.

Edge Cases and Examples

• Input: "a", 1, "a", 1 → 1.
• Input: "ab", 1, "abc", 1 → 0.
• Input: "a", 1000000, "a", 1 → 1000000.

Cycle detection handles all well.

Complexity Recap

• Cycle Detection: Time O(len(s1) * len(s2)), Space O(len(s1) + len(s2)).
• Brute Force: Time O(n1 * len(s1)), Space O(n1 * len(s1)).

Cycle detection’s the champ.

Key Takeaways

• Cycle Detection: Find rhythms fast.
• Brute Force: Write it all out.
• Python Tip: Patterns optimize—see [Python Basics](/python/basics).

Final Thoughts: Tally Those Repeats

LeetCode 466: Count The Repetitions in Python is a string-pattern odyssey. Cycle detection is your fast scribe, while brute force is a slow quill. Want more string challenges? Try LeetCode 459: Repeated Substring Pattern or LeetCode 3: Longest Substring Without Repeating Characters. Ready to count some chants? Head to Solve LeetCode 466 on LeetCode and tally it today—your coding skills are repetition-ready!