Count The Repetitions - Solution & Explanation
Problem Statement
We define str = [s, n] as the string str which consists of the string s concatenated n times.
- For example,
str == ["abc", 3] =="abcabcabc".
We define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1.
- For example,
s1 = "abc"can be obtained froms2 = "abdbec"based on our definition by removing the bolded underlined characters.
You are given two strings s1 and s2 and two integers n1 and n2. You have the two strings str1 = [s1, n1] and str2 = [s2, n2].
Return the maximum integer m such that str = [str2, m] can be obtained from str1.
Example 1:
Input: s1 = "acb", n1 = 4, s2 = "ab", n2 = 2 Output: 2
Example 2:
Input: s1 = "acb", n1 = 1, s2 = "acb", n2 = 1 Output: 1
Constraints:
1 <= s1.length, s2.length <= 100s1ands2consist of lowercase English letters.1 <= n1, n2 <= 106
Approach Overview
Problem Overview: You are given two strings s1 and s2 with repeat counts n1 and n2. The task is to determine how many times the sequence [s2, n2] can be obtained as a subsequence from the repeated string [s1, n1]. Characters must appear in order, but you can skip characters while matching.
Approach 1: Simulation using Pointers (Time: O(n1 * |s1|), Space: O(1))
This approach directly simulates building the repeated string [s1, n1] and tries to match characters from s2. Use two pointers: one iterating through characters of s1 and another tracking the current position in s2. Every time characters match, advance the s2 pointer. When the pointer reaches the end of s2, increment a counter and reset it to zero. After scanning s1 exactly n1 times, divide the total number of completed s2 matches by n2. This method relies purely on sequential scanning and subsequence matching logic, making it straightforward to implement. However, when n1 is very large, repeated scanning becomes inefficient because the same matching patterns repeat.
Approach 2: Cycle Detection Optimization (Time: ~O(|s1| * |s2|), Space: O(|s2|))
Repeated subsequence matching often forms cycles. After processing some repetitions of s1, the pointer inside s2 returns to a previously seen position. Once this happens, the same sequence of matches will repeat for the remaining blocks of s1. Store states using a map where the key is the current index in s2, and the value records how many s1 blocks and s2 matches have been processed. When the same s2 index appears again, a cycle is detected. You can compute how many full cycles fit into the remaining s1 repetitions and jump ahead instead of simulating each one. This drastically reduces runtime for large inputs. The idea resembles pattern repetition analysis often seen in string processing and dynamic programming style state reuse.
Recommended for interviews: Start with the pointer simulation to demonstrate the subsequence matching logic clearly. Then discuss the repeating pattern observation and optimize it with cycle detection. Interviewers typically expect the optimized solution because it shows you recognize repeated states and avoid redundant work, a common optimization pattern in advanced string problems.
Approach 1: Approach 1: Simulation using pointers
This approach attempts to simulate the process of generating strings str1 and counting how many times str2 can be obtained. It uses two pointers to track the current positions in s1 and s2, moving them accordingly to find subsequence matches.
This C solution employs two loops: the outer loop repeats s1 n1 times and the inner loop checks for matches between characters in s1 and s2. The logic counts complete occurrences of s2 and divides by n2 at completion.
Complexity
Time Complexity: O(n1 * len1 * len2) where len1 and len2 are lengths of s1 and s2 respectively. Space Complexity: O(1).
Approach 2: Approach 2: Cycle detection optimization
This approach optimizes the simulation by detecting and leveraging cycles. Once a cycle is detected in the repetition process, it calculates the outcomes in cycles to quickly compute the result, reducing the number of direct iterations required.
This C implementation detects cycle patterns in the process of iterating through s1 and s2. It optimizes by skipping over full cycle repetitions, leveraging recorded indices within the memoization table.
Complexity
Time Complexity: O(n1 * len1) in worst-case but optimized by cycle detection. Space Complexity: O(len1 * len2) for memoization table.
Approach 3: Preprocessing + Iteration
We preprocess the string s_2 such that for each starting position i, we calculate the next position j and the count of s_2 after matching a complete s_1, i.e., d[i] = (cnt, j), where cnt represents the count of s_2, and j represents the next position in the string s_2.
Next, we initialize j=0, and then loop n1 times. Each time, we add d[j][0] to the answer, and then update j=d[j][1].
The final answer is the count of s_2 that can be matched by n1 s_1, divided by n2.
The time complexity is O(m times n + n_1), and the space complexity is O(n). Where m and n are the lengths of s_1 and s_2 respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Simulation using pointers | Time Complexity: O(n1 * len1 * len2) where len1 and len2 are lengths of s1 and s2 respectively. Space Complexity: O(1). |
| Approach 2: Cycle detection optimization | Time Complexity: O(n1 * len1) in worst-case but optimized by cycle detection. Space Complexity: O(len1 * len2) for memoization table. |
| Preprocessing + Iteration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation using Pointers | O(n1 * |s1|) | O(1) | Good baseline solution when n1 is small or when demonstrating subsequence matching logic in interviews |
| Cycle Detection Optimization | ~O(|s1| * |s2|) | O(|s2|) | Best for large n1 where repeated patterns appear and skipping cycles avoids redundant simulation |
Video Solution
LeetCode 466. Count The Repetitions (Hard) | Dynamic Programming | C++ • Ascorbichelix • 3,427 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Count The Repetitions easy or hard?
Count The Repetitions Python/Java solution
How to solve Count The Repetitions in O(n)?
What is the best approach for Count The Repetitions?
Is Count The Repetitions asked at Google/Amazon/Meta?
What data structure is used in Count The Repetitions?
What is the time complexity of Count The Repetitions?
Ready to solve this problem?
Practice Count The Repetitions with our built-in code editor and test cases.
Practice on FleetCode