LeetCode 466 - Count The Repetitions

Difficulty: 🔴 Hard
Topics: Two Pointers, String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to find the maximum number of times a string str2 can be obtained from another string str1 when both are repeated multiple times. Specifically, str1 is the string s1 repeated n1 times, and str2 is the string s2 repeated n2 times. To "obtain" str2 from str1 means that we can remove characters from str1 without rearranging the remaining characters so that it matches str2.

In simpler terms, we are trying to figure out how many full repetitions of s2 can fit into multiple repetitions of s1, considering that we can skip characters in s1 but cannot reorder them. The output is an integer m representing the maximum number of full str2 repetitions achievable.

The constraints are important: the lengths of s1 and s2 are small (up to 100), but n1 and n2 can be very large (up to 1,000,000). This means that a naive approach that explicitly constructs the repeated strings will be too slow and memory-intensive. Instead, we need to rely on patterns and repetition cycles in the matching process.

Key edge cases include situations where s2 contains characters not in s1, cases where n1 is small or equal to 1, or where s1 and s2 are identical. These conditions could break naive string-building approaches but must be handled correctly in an optimal solution.

Approaches

The brute-force approach is straightforward: repeatedly concatenate s1 to build str1 and try to match s2 sequentially using a pointer. Every time a full s2 is matched, increment a counter. This approach is correct because it directly follows the problem definition. However, it is too slow because n1 and n2 can reach up to one million, making full string construction infeasible in time and memory.

The optimal approach leverages the observation that the matching process has cycles due to the repeated nature of s1 and s2. After some repetitions, the relative position in s2 when starting a new s1 repetition begins to repeat. Once we detect this cycle, we can compute the total number of matches using arithmetic instead of simulating every repetition. This reduces the complexity dramatically because we avoid iterating through every character in the full str1.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n1 * len(s1) * len(s2))	O(n1 * len(s1))	Builds the full repeated string and simulates matching; too slow for large n1
Optimal	O(len(s1) * len(s2) + n1)	O(len(s2))	Detects cycles to jump over repetitions efficiently

Algorithm Walkthrough

Initialize counters: s1_count for how many times we have used s1, s2_count for how many times s2 has been fully matched, and index to track our position in s2.
Use a dictionary recall to store the state after each repetition of s1. The key is the current index in s2, and the value is a tuple (s1_count, s2_count).
Start a loop that increments s1_count each time we process one repetition of s1.
Inside the loop, iterate over s1. For each character, if it matches the current character in s2 at position index, increment index. If index reaches the length of s2, reset it to zero and increment s2_count.
After processing one s1, check if the current index has appeared before in recall. If it has, a cycle is detected.
Compute how many full cycles can fit into the remaining repetitions of s1 and add the corresponding s2_count in bulk.
Continue processing any remaining repetitions of s1 after the cycles.
Finally, return s2_count // n2 to determine how many full str2 sequences can be obtained.

The algorithm works because the repeated matching process will eventually enter a cycle due to the finite number of positions in s2. Once the cycle is detected, we can compute the contributions of all repetitions in constant time per cycle, ensuring efficiency even for very large n1.

Python Solution

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        if n1 == 0:
            return 0
        
        s1_count = 0
        s2_count = 0
        index = 0
        recall = dict()
        
        while s1_count < n1:
            s1_count += 1
            for char in s1:
                if char == s2[index]:
                    index += 1
                    if index == len(s2):
                        index = 0
                        s2_count += 1
            
            if index in recall:
                prev_s1_count, prev_s2_count = recall[index]
                cycle_s1_count = s1_count - prev_s1_count
                cycle_s2_count = s2_count - prev_s2_count
                remaining_s1 = n1 - s1_count
                cycles = remaining_s1 // cycle_s1_count
                s1_count += cycles * cycle_s1_count
                s2_count += cycles * cycle_s2_count
            else:
                recall[index] = (s1_count, s2_count)
        
        return s2_count // n2

This Python implementation uses a dictionary to detect cycles based on the current index in s2. It iterates over s1 once per repetition, tracking how many times s2 has been matched. Once a cycle is found, the algorithm jumps ahead by multiples of the cycle, which prevents unnecessary repeated simulation. The final division by n2 gives the maximum number of full str2 repetitions.

Go Solution

func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
    if n1 == 0 {
        return 0
    }

    s1Count, s2Count, index := 0, 0, 0
    recall := make(map[int][2]int)

    for s1Count < n1 {
        s1Count++
        for i := 0; i < len(s1); i++ {
            if s1[i] == s2[index] {
                index++
                if index == len(s2) {
                    index = 0
                    s2Count++
                }
            }
        }

        if val, ok := recall[index]; ok {
            prevS1Count, prevS2Count := val[0], val[1]
            cycleS1Count := s1Count - prevS1Count
            cycleS2Count := s2Count - prevS2Count
            remainingS1 := n1 - s1Count
            cycles := remainingS1 / cycleS1Count
            s1Count += cycles * cycleS1Count
            s2Count += cycles * cycleS2Count
        } else {
            recall[index] = [2]int{s1Count, s2Count}
        }
    }

    return s2Count / n2
}

The Go version mirrors the Python solution closely. The main differences include using a fixed-size array [2]int for storing tuples in the map and explicit type handling for integer division. The logic for detecting cycles and jumping over repetitions is identical.

Worked Examples

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

Step	s1_count	index	s2_count	recall
Initial	0	0	0	{}
1	1	1	1	{1:(1,1)}
2	2	2	2	{1:(1,1), 2:(2,2)}
3	3	0	2	{0:(3,2)}
4	4	1	3	{0:(3,2), 1:(4,3)}

Result: s2_count // n2 = 3 // 2 = 1

Example 2: s1 = "acb", n1 = 1, s2 = "acb", n2 = 1

Step	s1_count	index	s2_count	recall
Initial	0	0	0	{}
1	1	0	1	{0:(1,1)}

Result: s2_count // n2 = 1 // 1 = 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(len(s1) * len(s2) + n1)	Each character of `s1` is processed per repetition, plus cycle detection jumps through `n1` efficiently
Space	O(len(s2))	Stores the state for each unique index in `s2`, which is at most len(s2)

The main time savings come from detecting cycles, which allows