#466

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count The Repetitions

This problem requires counting how many times a repeated string s2 fits as a subsequence within a repeated string s1 using dynamic programming.

string dynamic programming

Problem Statement

Given two strings s1 and s2 and integers n1 and n2, define str1 as s1 repeated n1 times and str2 as s2 repeated n2 times. Determine the maximum integer M such that M copies of str2 can be formed as subsequences from str1.

A string s can be obtained from another string t if we can remove some characters from t without reordering the remaining characters. Your task is to implement an efficient algorithm to calculate how many full repetitions of str2 appear in str1 while considering large n1 and n2 values.

Examples

Example 1

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

Output: 2

Example details omitted.

Example 2

Input: s1 = "acb", n1 = 1, s2 = "acb", n2 = 1

Output: 1

Example details omitted.

Constraints

1 <= s1.length, s2.length <= 100
s1 and s2 consist of lowercase English letters.
1 <= n1, n2 <= 106

Solution Approach

State Transition Tracking

Iterate through str1 while maintaining a pointer in s2. Each time a character matches, advance the pointer in s2. Use a dictionary to record the state after each full s1 iteration to detect cycles and speed up counting.

Cycle Detection Optimization

Once a previously seen state repeats, a cycle is detected. Compute the number of complete cycles that fit into the remaining iterations of str1 to multiply the count of str2 occurrences without scanning every character.

Final Count Calculation

Sum the counts from initial iterations before the cycle, the cycle repetitions, and any remaining unmatched segment to obtain the total occurrences. Divide by n2 to get the maximum M of full str2 repetitions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(|s1| + |s2|) in practice due to cycle optimization, instead of naive O(n1*|s1|*|s2|). Space complexity is O(|s2|) for storing states to detect cycles.

What Interviewers Usually Probe

Expect you to recognize subsequence patterns within repeated strings.
Look for cycle detection to optimize repeated sequence counting.
Consider how state transitions map the matching progress of s2 inside s1.

Common Pitfalls or Variants

Common pitfalls

Attempting naive iteration over str1 fully will time out due to large n1.
Ignoring cycles or repeated states leads to unnecessary computation.
Misaligning the subsequence pointer resets after each s1 repetition.

Follow-up variants

Compute the maximum number of s2 occurrences in str1 when n1 is extremely large and cannot be fully materialized.
Modify the problem to return the positions in str1 where each s2 repetition ends.
Change s2 to allow optional characters, increasing the dynamic programming state complexity.

FAQ

What is the core pattern used in Count The Repetitions?

The problem relies on state transition dynamic programming, tracking the matching position in s2 through repeated s1 iterations.

How do cycles improve performance in this problem?

Detecting repeating states allows us to skip redundant iterations and multiply counts, avoiding timeouts for large n1.

Can we use a brute-force approach for small inputs?

Yes, iterating over all characters works for small n1 and n2, but it fails for the upper constraint limits.

What common mistakes lead to wrong answers?

Not resetting the s2 pointer correctly per s1 repetition or ignoring overlapping cycles causes miscounting.

Why does dynamic programming fit Count The Repetitions?

DP efficiently tracks progress across repeated sequences and handles state transitions, which is essential for counting subsequences in repeated strings.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        n = len(s2)
        d = {}
        for i in range(n):
            cnt = 0
            j = i
            for c in s1:
                if c == s2[j]:
                    j += 1
                if j == n:
                    cnt += 1
                    j = 0
            d[i] = (cnt, j)

        ans = 0
        j = 0
        for _ in range(n1):
            cnt, j = d[j]
            ans += cnt
        return ans // n2

Continue Practicing

#467 unique substrings in wraparound string #472 concatenated words #474 ones and zeroes