Watch 9 video solutions for Count The Repetitions, a hard level problem involving String, Dynamic Programming. This walkthrough by Ascorbicindio has 3,268 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |