We define str = [s, n] as the string str which consists of the string s concatenated n times.
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.
s1 = "abc" can be obtained from s2 = "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 <= 100s1 and s2 consist of lowercase English letters.1 <= n1, n2 <= 106Problem 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.
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.
Time Complexity: O(n1 * len1 * len2) where len1 and len2 are lengths of s1 and s2 respectively. Space Complexity: O(1).
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.
Time Complexity: O(n1 * len1) in worst-case but optimized by cycle detection. Space Complexity: O(len1 * len2) for memoization table.
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
LeetCode 466. Count The Repetitions (Hard) | Dynamic Programming | C++ • Ascorbicindio • 3,268 views views
Watch 8 more video solutions →Practice Count The Repetitions with our built-in code editor and test cases.
Practice on FleetCode