Count The Repetitions

Hard

#0453Time: O(n1 * s1.length). We have a loop that runs `n1` times, and inside it, another loop runs `s1.length` times. Given `n1` can be up to 10^6 and `s1.length` up to 100, this can be up to 10^8 operations, which is too slow.Space: O(1), as we only use a few variables to keep track of the counts and indices.

Patterns

Dynamic Programming

Data structures

String

Prompt

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 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 <= 100
s1 and s2 consist of lowercase English letters.
1 <= n1, n2 <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We can think of str1 as s1 concatenated n1 times. We then iterate through this conceptual large string, character by character, trying to form as many non-overlapping subsequences of s2 as possible. We maintain a count of how many times s2 has been fully formed. Since n1 can be very large, we don't build the full str1 string in memory. Instead, we use nested loops: an outer loop that runs n1 times (for each s1 block) and an inner loop that iterates through the characters of s1.

Algorithm

Initialize s2_count = 0 to count the total number of s2 repetitions found.
Initialize s2_idx = 0 as a pointer to the current character we are looking for in s2.
Loop n1 times, with each loop representing one concatenation of s1.
Inside this loop, iterate through each character of s1.
If the character from s1 matches the character s2.charAt(s2_idx), it means we found the next character of a subsequence s2. Increment s2_idx.
If s2_idx becomes equal to s2.length(), it means we have successfully found one complete s2 subsequence. Increment s2_count and reset s2_idx to 0 to start searching for the next s2.
After the loops complete, s2_count holds the total number of s2 repetitions that can be obtained from str1 = [s1, n1].
The problem asks for the maximum m such that [str2, m] can be obtained. str2 itself consists of n2 repetitions of s2. So, [str2, m] consists of m * n2 repetitions of s2.
The maximum m is therefore s2_count / n2.

Walkthrough

The brute-force method involves a straightforward simulation. We need to find how many times s2 can be formed as a subsequence from s1 repeated n1 times. We can maintain a pointer, s2_idx, for the current character we are searching for in s2, and a counter, s2_count, for the number of times we have successfully formed s2.

We iterate n1 times, and in each iteration, we scan through s1. During the scan, if we find a character that matches s2.charAt(s2_idx), we advance the pointer s2_idx. When s2_idx reaches the end of s2, it signifies that one instance of s2 has been completed. We then increment s2_count and reset s2_idx to 0 to begin the search for the next instance of s2.

After iterating through all n1 blocks of s1, s2_count will give us the total number of s2 repetitions. The final answer m is s2_count / n2.

1class Solution {2    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {3        long s2_count = 0;4        int s2_idx = 0;5        int s1_len = s1.length();6        int s2_len = s2.length();7 8        for (int i = 0; i < n1; i++) {9            for (int j = 0; j < s1_len; j++) {10                if (s1.charAt(j) == s2.charAt(s2_idx)) {11                    s2_idx++;12                    if (s2_idx == s2_len) {13                        s2_idx = 0;14                        s2_count++;15                    }16                }17            }18        }19 20        return (int) (s2_count / n2);21    }22}

Complexity

Time

O(n1 * s1.length). We have a loop that runs `n1` times, and inside it, another loop runs `s1.length` times. Given `n1` can be up to 10^6 and `s1.length` up to 100, this can be up to 10^8 operations, which is too slow.

Space

O(1), as we only use a few variables to keep track of the counts and indices.

Trade-offs

Pros

Simple to understand and implement.
Low memory usage.

Cons

The time complexity is too high for the given constraints on n1 and s1.length, leading to a Time Limit Exceeded (TLE) error on most platforms.

The brute-force approach is inefficient because n1 is large. We can observe that the simulation has a repeating pattern. The state of the simulation at the end of processing each s1 block is determined by the index in s2 (s2_idx) that we are currently searching for. Since there are a limited number of states (at most s2.length()), the sequence of states must eventually repeat, forming a cycle. By detecting this cycle, we can fast-forward the simulation instead of iterating n1 times.

Algorithm

The state of our simulation after processing a block of s1 can be uniquely identified by s2_idx, the index of the character we are currently searching for in s2.
Since s2_idx can only have s2.length() different values (0 to s2.length()-1), the state must eventually repeat.
When a state s2_idx repeats, we have found a cycle. The simulation from this point onwards will repeat the same pattern of s2 counts and s2_idx transitions.
We can use a hash map to detect this cycle. The map, say recall, will store the s1_count and s2_count at the moment a particular s2_idx is first seen.
We simulate block by block. Before processing a block, we check if the current s2_idx is in our recall map.
If it is, we have found a cycle. We can calculate:
1. The prefix: the number of s1 blocks and s2 counts before the cycle began.
2. The cycle: the number of s1 blocks and s2 counts in one full cycle.
With this information, we can calculate how many full cycles fit in the remaining n1 blocks and add the corresponding s2 counts.
Finally, we calculate the s2 counts for the suffix (the remaining blocks that don't form a full cycle) and add them to the total.
The total s2 count is the sum from the prefix, the full cycles, and the suffix. The final answer is this total divided by n2.

Walkthrough

This optimized approach avoids the costly full simulation by identifying a cycle. We iterate through s1 blocks one by one, keeping track of s1_count, s2_count, and s2_idx.

We use two hash maps for tracking history:

s2_idx_to_s1_count: Maps an s2_idx to the s1_count when that s2_idx was first encountered at the start of an s1 block.
s1_count_to_s2_count: Maps an s1_count to the total s2_count accumulated after processing that many s1 blocks.

As we iterate, before processing the s1_i-th block, we check if the current s2_idx is already in s2_idx_to_s1_count. If it is, a cycle is detected.

Prefix: The part of the simulation before the cycle starts. Its length is prev_s1_i blocks, and it yields prev_s2_count repetitions of s2.
Cycle: The repeating part. Its length in s1 blocks and the number of s2s it produces can be calculated from the stored history.

Once the cycle is found, we can calculate the total s2 count without further simulation: total_s2s = (prefix_s2s) + (num_cycles * cycle_s2s) + (suffix_s2s)

The number of cycles is determined by how many times the cycle pattern fits into the remaining s1 blocks. The suffix count is found by looking up the history for the small number of remaining blocks.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {6        // Map to detect cycle: s2_idx -> s1_count7        Map<Integer, Integer> s2_idx_to_s1_count = new HashMap<>();8        // History of s2 counts: s1_count -> s2_count9        Map<Integer, Integer> s1_count_to_s2_count = new HashMap<>();10        11        int s2_idx = 0;12        int s2_count = 0;13        14        for (int s1_i = 0; s1_i < n1; s1_i++) {15            // Check for cycle start16            if (s2_idx_to_s1_count.containsKey(s2_idx)) {17                // Cycle detected18                int prev_s1_i = s2_idx_to_s1_count.get(s2_idx);19                int prev_s2_count = s1_count_to_s2_count.get(prev_s1_i);20                21                // Cycle pattern22                int cycle_s1_len = s1_i - prev_s1_i;23                int cycle_s2_count = s2_count - prev_s2_count;24                25                // Calculate total s2's using the cycle pattern26                long remaining_s1_after_prefix = n1 - prev_s1_i;27                long num_cycles = remaining_s1_after_prefix / cycle_s1_len;28                29                long total_s2 = (long)prev_s2_count + num_cycles * cycle_s2_count;30                31                // Suffix part32                long suffix_s1_len = remaining_s1_after_prefix % cycle_s1_len;33                int suffix_s1_end_count = prev_s1_i + (int)suffix_s1_len;34                int suffix_s2_count = s1_count_to_s2_count.get(suffix_s1_end_count) - prev_s2_count;35                36                total_s2 += suffix_s2_count;37                38                return (int) (total_s2 / n2);39            }40            41            // Store history before processing the current s1 block42            s2_idx_to_s1_count.put(s2_idx, s1_i);43            s1_count_to_s2_count.put(s1_i, s2_count);44            45            // Simulate one block of s146            for (int j = 0; j < s1.length(); j++) {47                if (s1.charAt(j) == s2.charAt(s2_idx)) {48                    s2_idx++;49                    if (s2_idx == s2.length()) {50                        s2_idx = 0;51                        s2_count++;52                    }53                }54            }55        }56        57        // No cycle found within n1 blocks (n1 was small)58        return s2_count / n2;59    }60}

Complexity

Time

O(s1.length * s2.length). The simulation loop runs at most `s2.length` times before a cycle is detected. Inside the loop, we iterate through `s1`, which takes `O(s1.length)`. Therefore, the complexity is dominated by the cycle detection part.

Space

O(s2.length). The hash maps will store at most `s2.length` entries, as this is the maximum number of unique states (`s2_idx`) before a cycle must occur.

Trade-offs

Pros

Highly efficient and passes within the time limits for large inputs.
Correctly handles the large constraints by avoiding redundant computations.

Cons

The logic is more complex to implement correctly compared to the brute-force approach.
Requires careful handling of prefix, cycle, and suffix calculations to avoid off-by-one errors.

Solutions

Solution

1class Solution {2public3  int getMaxRepetitions(String s1, int n1, String s2, int n2) {4    int m = s1.length(), n = s2.length();5    int[][] d = new int[n][0];6    for (int i = 0; i < n; ++i) {7      int j = i;8      int cnt = 0;9      for (int k = 0; k < m; ++k) {10        if (s1.charAt(k) == s2.charAt(j)) {11          if (++j == n) {12            j = 0;13            ++cnt;14          }15        }16      }17      d[i] = new int[]{cnt, j};18    }19    int ans = 0;20    for (int j = 0; n1 > 0; --n1) {21      ans += d[j][0];22      j = d[j][1];23    }24    return ans / n2;25  }26}

1class Solution {2public:3  int getMaxRepetitions(string s1, int n1, string s2, int n2) {4    int m = s1.size(), n = s2.size();5    vector<pair<int, int>> d;6    for (int i = 0; i < n; ++i) {7      int j = i;8      int cnt = 0;9      for (int k = 0; k < m; ++k) {10        if (s1[k] == s2[j]) {11          if (++j == n) {12            ++cnt;13            j = 0;14          }15        }16      }17      d.emplace_back(cnt, j);18    }19    int ans = 0;20    for (int j = 0; n1; --n1) {21      ans += d[j].first;22      j = d[j].second;23    }24    return ans / n2;25  }26};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem