Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Count The Repetitions solution and explanation

HardDynamic ProgrammingString6 min read36.0% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Count The Repetitions
9:17
LeetCode 466. Count The Repetitions (Hard) | Dynamic Programming | C++Ascorbichelix · 9:17 · 3K viewsWatch on YouTube
7 more videos on this problem
  1. LeetCode 466. Count The Repetitions (Hard) | Dynamic Programming | C++Ascorbichelix · 9:17 · 3K views
  2. 466. Count The Repetitions 统计重复个数【LeetCode 力扣题解】LeetCode 力扣 · 14:38 · 962 views
  3. LeetCode #466 Count The Repetitions【熊猫刷题】莲子熊猫 · 5:21 · 229 views
  4. LeetCode 466: Count The RepetitionsAlitaCode · 29:58 · 169 views
  5. No Sound Leetcode 466: Count The RepetitionsExtremeProgrammer · 1:44 · 74 views
  6. Chatgpt C++ leetcode 466. Count The RepetitionsWindows 8.1 Tails Prower Ultra · 9:43 · 8 views
  7. ข้อ 466. Count The Repetitions | LeetCodeThakorn Jareonrat · 18:28 · 7 views
  8. Count The Repetitions — LeetCode #466 | Python Algorithm VisualizationBenabub · 2:34 · 4 views

The problem

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 <= 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.

def getMaxRepetitions(s1, n1, s2, n2):
    len1, len2 = len(s1), len(s2)
    count1 = count2 = 0
    i = j = 0
    while count1 < n1:
        if s1[i] == s2[j]:
            j += 1
            if j == len2:
                count2 += 1
                j = 0
        i += 1
        if i == len1:
            count1 += 1
            i = 0
    return count2 // n2

print(getMaxRepetitions("acb", 4, "ab", 2)) # Output: 2
print(getMaxRepetitions("acb", 1, "acb", 1)) # Output: 1
public class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int len1 = s1.length(), len2 = s2.length();
        int count1 = 0, count2 = 0;
        int i = 0, j = 0;
        while (count1 < n1) {
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
                if (j == len2) {
                    count2++;
                    j = 0;
                }
            }
            i++;
            if (i == len1) {
                count1++;
                i = 0;
            }
        }
        return count2 / n2;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.getMaxRepetitions("acb", 4, "ab", 2)); // Output: 2
        System.out.println(solution.getMaxRepetitions("acb", 1, "acb", 1)); // Output: 1
    }
}
#include <iostream>
#include <string>
using namespace std;

int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    int len1 = s1.length(), len2 = s2.length();
    int count1 = 0, count2 = 0;
    int i = 0, j = 0;
    while (count1 < n1) {
        if (s1[i] == s2[j]) {
            j++;
            if (j == len2) {
                count2++;
                j = 0;
            }
        }
        i++;
        if (i == len1) {
            count1++;
            i = 0;
        }
    }
    return count2 / n2;
}

int main() {
    cout << getMaxRepetitions("acb", 4, "ab", 2) << endl; // Output: 2
    cout << getMaxRepetitions("acb", 1, "acb", 1) << endl; // Output: 1
    return 0;
}
function getMaxRepetitions(s1, n1, s2, n2) {
    let len1 = s1.length, len2 = s2.length;
    let count1 = 0, count2 = 0;
    let i = 0, j = 0;
    while (count1 < n1) {
        if (s1[i] === s2[j]) {
            j++;
            if (j === len2) {
                count2++;
                j = 0;
            }
        }
        i++;
        if (i === len1) {
            count1++;
            i = 0;
        }
    }
    return Math.floor(count2 / n2);
}

console.log(getMaxRepetitions("acb", 4, "ab", 2)); // Output: 2
console.log(getMaxRepetitions("acb", 1, "acb", 1)); // Output: 1;
#include <stdio.h>
#include <string.h>

int getMaxRepetitions(char* s1, int n1, char* s2, int n2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    int count1 = 0, count2 = 0;
    int i = 0, j = 0;
    while (count1 < n1) {
        if (s1[i] == s2[j]) {
            j++;
            if (j == len2) {
                count2++;
                j = 0;
            }
        }
        i++;
        if (i == len1) {
            count1++;
            i = 0;
        }
    }
    return count2 / n2;
}

int main() {
    printf("%d\n", getMaxRepetitions("acb", 4, "ab", 2)); // Output: 2
    printf("%d\n", getMaxRepetitions("acb", 1, "acb", 1)); // Output: 1
    return 0;
}
using System;

public class Solution {
    public int GetMaxRepetitions(string s1, int n1, string s2, int n2) {
        int len1 = s1.Length, len2 = s2.Length;
        int count1 = 0, count2 = 0;
        int i = 0, j = 0;
        while (count1 < n1) {
            if (s1[i] == s2[j]) {
                j++;
                if (j == len2) {
                    count2++;
                    j = 0;
                }
            }
            i++;
            if (i == len1) {
                count1++;
                i = 0;
            }
        }
        return count2 / n2;
    }

    public static void Main() {
        Solution solution = new Solution();
        Console.WriteLine(solution.GetMaxRepetitions("acb", 4, "ab", 2)); // Output: 2
        Console.WriteLine(solution.GetMaxRepetitions("acb", 1, "acb", 1)); // Output: 1
    }
}

The Python version retains the same basic logic, looping through the length of s1 for n1 counts and checking matches with s2 concurrently.

Complexity

Time Complexity: O(n1 * len1 * len2) where len1 and len2 are lengths of s1 and s2 respectively. Space Complexity: O(1).

Try this approach in the editor

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.

def getMaxRepetitions(s1, n1, s2, n2):
    len1, len2 = len(s1), len(s2)
    memo = [-1] * (len2 + 1)
    count1 = count2 = 0
    i = j = 0

    while count1 < n1 and memo[j] == -1:
        memo[j] = count2 * len1 + i
        for k in range(len1):
            if i == len1:
                i, count1 = 0, count1 + 1
            if s1[i] == s2[j]:
                j += 1
                if j == len2:
                    j, count2 = 0, count2 + 1
            i += 1

    if count1 >= n1:
        return count2 // n2

    cycle_enclosed = count1 % len1
    cycle_len = (count2 * len1 + i) - memo[cycle_enclosed]
    cycle_count2 = count2 - (memo[cycle_enclosed] // len1)
    cycles = (n1 - count1) // cycle_len
    count2 += cycles * cycle_count2
    count1 += cycles * cycle_len
    while count1 < n1:
        for k in range(len1):
            if i == len1:
                i, count1 = 0, count1 + 1
            if s1[i] == s2[j]:
                j += 1
                if j == len2:
                    j, count2 = 0, count2 + 1
            i += 1
    return count2 // n2

print(getMaxRepetitions("acb", 4, "ab", 2)) # Output: 2
print(getMaxRepetitions("acb", 1, "acb", 1)) # Output: 1
import java.util.*;

public class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int len1 = s1.length(), len2 = s2.length();
        int[] memo = new int[len2 + 1];
        Arrays.fill(memo, -1);
        int count1 = 0, count2 = 0;
        int i = 0, j = 0;

        for (int cycle = 0; count1 < n1 && memo[j] == -1; cycle = count1 % len1) {
            memo[j] = count2 * len1 + i;
            for (int k = 0; k < len1; ++i, ++k) {
                if (i == len1) {
                    i = 0; count1++;
                }
                if (s1.charAt(i) == s2.charAt(j)) {
                    j++;
                    if (j == len2) {
                        j = 0; count2++;
                    }
                }
            }
        }
        if (count1 >= n1) return count2 / n2;

        int cycle_enclosed = count1 % len1;
        int cycle_len = (count2 * len1 + i) - memo[cycle_enclosed];
        int cycle_count2 = count2 - (memo[cycle_enclosed] / len1);
        int cycles = (n1 - count1) / cycle_len;
        count2 += cycles * cycle_count2;
        count1 += cycles * cycle_len;
        while (count1 < n1) {
            for (int k = 0; k < len1; ++i, ++k) {
                if (i == len1) {
                    i = 0; count1++;
                }
                if (s1.charAt(i) == s2.charAt(j)) {
                    j++;
                    if (j == len2) {
                        j = 0; count2++;
                    }
                }
            }
        }
        return count2 / n2;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.getMaxRepetitions("acb", 4, "ab", 2)); // Output: 2
        System.out.println(solution.getMaxRepetitions("acb", 1, "acb", 1)); // Output: 1
    }
}
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    int len1 = s1.length(), len2 = s2.length();
    vector<vector<int>> memo(len1 + 1, vector<int>(len2 + 1, -1));
    int count1 = 0, count2 = 0;
    int i = 0, j = 0;

    for (int cycle = 0; count1 < n1 && memo[count1 % len1][j] == -1; cycle = count1 % len1) {
        memo[cycle][j] = count2 * len1 + i;
        for (int k = 0; k < len1; ++i, ++k) {
            if (i == len1) {
                i = 0; count1++;
            }
            if (s1[i] == s2[j]) {
                j++;
                if (j == len2) {
                    j = 0; count2++;
                }
            }
        }
    }
    if (count1 >= n1) return count2 / n2;

    int cycle_enclosed = count1 % len1;
    int cycle_len = (count2 * len1 + i) - memo[cycle_enclosed][j];
    int cycle_count2 = count2 - (memo[cycle_enclosed][j] / len1);
    int cycles = (n1 - count1) / cycle_len;
    count2 += cycles * cycle_count2;
    count1 += cycles * cycle_len;
    while (count1 < n1) {
        for (int k = 0; k < len1; ++i, ++k) {
            if (i == len1) {
                i = 0; count1++;
            }
            if (s1[i] == s2[j]) {
                j++;
                if (j == len2) {
                    j = 0; count2++;
                }
            }
        }
    }
    return count2 / n2;
}

int main() {
    cout << getMaxRepetitions("acb", 4, "ab", 2) << endl; // Output: 2
    cout << getMaxRepetitions("acb", 1, "acb", 1) << endl; // Output: 1
    return 0;
}
function getMaxRepetitions(s1, n1, s2, n2) {
    var len1 = s1.length, len2 = s2.length;
    var memo = new Array(len2 + 1).fill(-1);
    var count1 = 0, count2 = 0;
    var i = 0, j = 0;

    while (count1 < n1 && memo[j] === -1) {
        memo[j] = count2 * len1 + i;
        for (var k = 0; k < len1; i++, k++) {
            if (i === len1) {
                i = 0; count1++;
            }
            if (s1[i] === s2[j]) {
                j++;
                if (j === len2) {
                    j = 0; count2++;
                }
            }
        }
    }
    if (count1 >= n1) return Math.floor(count2 / n2);

    var cycle_enclosed = count1 % len1;
    var cycle_len = (count2 * len1 + i) - memo[cycle_enclosed];
    var cycle_count2 = count2 - Math.floor(memo[cycle_enclosed] / len1);
    var cycles = Math.floor((n1 - count1) / cycle_len);
    count2 += cycles * cycle_count2;
    count1 += cycles * cycle_len;
    while (count1 < n1) {
        for (var k = 0; k < len1; i++, k++) {
            if (i === len1) {
                i = 0; count1++;
            }
            if (s1[i] === s2[j]) {
                j++;
                if (j === len2) {
                    j = 0; count2++;
                }
            }
        }
    }
    return Math.floor(count2 / n2);
}

console.log(getMaxRepetitions("acb", 4, "ab", 2)); // Output: 2
console.log(getMaxRepetitions("acb", 1, "acb", 1)); // Output: 1;
#include <stdio.h>
#include <string.h>
#define MAXN 102

int getMaxRepetitions(char* s1, int n1, char* s2, int n2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    int memo[MAXN][MAXN];
    memset(memo, -1, sizeof(memo));
    int count1 = 0, count2 = 0;
    int i = 0, j = 0, k;

    for (int cycle = 0; count1 < n1 && memo[cycle][j] == -1; cycle = count1 % len1) {
        memo[cycle][j] = count2 * len1 + i;
        for (k = 0; k < len1; ++i, ++k) {
            if (i == len1) {
                i = 0, count1++;
            }
            if (s1[i] == s2[j]) {
                j++;
                if (j == len2) {
                    j = 0;
                    count2++;
                }
            }
        }
    }
    if (count1 >= n1) return count2 / n2;
    int cycle_enclosed = count1 % len1;
    int cycle_len = (count2 * len1 + i) - memo[cycle_enclosed][j];
    int cycle_count2 = count2 - (memo[cycle_enclosed][j] / len1);
    int cycles = (n1 - count1) / cycle_len;
    count2 += cycles * cycle_count2;
    count1 += cycles * cycle_len;
    while (count1 < n1) {
        for (k = 0; k < len1; ++i, ++k) {
            if (i == len1) {
                i = 0, count1++;
            }
            if (s1[i] == s2[j]) {
                j++;
                if (j == len2) {
                    j = 0;
                    count2++;
                }
            }
        }
    }
    return count2 / n2;
}

int main() {
    printf("%d\n", getMaxRepetitions("acb", 4, "ab", 2)); // Output: 2
    printf("%d\n", getMaxRepetitions("acb", 1, "acb", 1)); // Output: 1
    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    public int GetMaxRepetitions(string s1, int n1, string s2, int n2) {
        int len1 = s1.Length, len2 = s2.Length;
        int[] memo = new int[len2 + 1];
        Array.Fill(memo, -1);
        int count1 = 0, count2 = 0;
        int i = 0, j = 0;

        while (count1 < n1 && memo[j] == -1) {
            memo[j] = count2 * len1 + i;
            for (int k = 0; k < len1; ++i, ++k) {
                if (i == len1) {
                    i = 0; count1++;
                }
                if (s1[i] == s2[j]) {
                    j++;
                    if (j == len2) {
                        j = 0; count2++;
                    }
                }
            }
        }
        if (count1 >= n1) return count2 / n2;

        int cycle_enclosed = count1 % len1;
        int cycle_len = (count2 * len1 + i) - memo[cycle_enclosed];
        int cycle_count2 = count2 - (memo[cycle_enclosed] / len1);
        int cycles = (n1 - count1) / cycle_len;
        count2 += cycles * cycle_count2;
        count1 += cycles * cycle_len;
        while (count1 < n1) {
            for (int k = 0; k < len1; ++i, ++k) {
                if (i == len1) {
                    i = 0; count1++;
                }
                if (s1[i] == s2[j]) {
                    j++;
                    if (j == len2) {
                        j = 0; count2++;
                    }
                }
            }
        }
        return count2 / n2;
    }

    public static void Main() {
        Solution solution = new Solution();
        Console.WriteLine(solution.GetMaxRepetitions("acb", 4, "ab", 2)); // Output: 2
        Console.WriteLine(solution.GetMaxRepetitions("acb", 1, "acb", 1)); // Output: 1
    }
}

Python's implementation uses a list to track cycle occurrences, allowing it to efficiently calculate the overall repetitions of s2 possible within s1.

Complexity

Time Complexity: O(n1 * len1) in worst-case but optimized by cycle detection. Space Complexity: O(len1 + len2) for memoization.

Try this approach in the editor

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.

function getMaxRepetitions(s1: string, n1: number, s2: string, n2: number): number {
    const n = s2.length;
    const d: number[][] = new Array(n).fill(0).map(() => new Array(2).fill(0));
    for (let i = 0; i < n; ++i) {
        let j = i;
        let cnt = 0;
        for (const c of s1) {
            if (c === s2[j]) {
                if (++j === n) {
                    j = 0;
                    ++cnt;
                }
            }
        }
        d[i] = [cnt, j];
    }
    let ans = 0;
    for (let j = 0; n1 > 0; --n1) {
        ans += d[j][0];
        j = d[j][1];
    }
    return Math.floor(ans / n2);
}
func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) (ans int) {
	n := len(s2)
	d := make([][2]int, n)
	for i := 0; i < n; i++ {
		j := i
		cnt := 0
		for k := range s1 {
			if s1[k] == s2[j] {
				j++
				if j == n {
					cnt++
					j = 0
				}
			}
		}
		d[i] = [2]int{cnt, j}
	}
	for j := 0; n1 > 0; n1-- {
		ans += d[j][0]
		j = d[j][1]
	}
	ans /= n2
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
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.

Preprocessing + Iteration–

Complexity analysis

ApproachTimeSpaceWhen to Use
Simulation using PointersO(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

Frequently asked questions

Is Count The Repetitions easy or hard?

Count The Repetitions is classified as a Hard problem because the straightforward simulation can be slow for large inputs. The key difficulty is recognizing that the matching process eventually repeats and using cycle detection to skip redundant work.

Count The Repetitions Python/Java solution

Both Python and Java implementations follow the same logic: simulate subsequence matching between repeated s1 and s2 while tracking the current index in s2. The optimized version stores previously seen states in a map to detect cycles and jump ahead when patterns repeat.

How to solve Count The Repetitions in O(n)?

Strict O(n) time is not guaranteed because matching depends on both |s1| and |s2|. However, cycle detection significantly reduces redundant scans by identifying repeating states of the s2 pointer. Once a cycle is found, you can jump across many repetitions of s1 in constant time.

What is the best approach for Count The Repetitions?

The most efficient approach uses cycle detection during the simulation of repeated strings. By storing the current index in s2 after each pass of s1, you can detect repeating states and skip entire cycles. This reduces redundant work and improves performance to roughly O(|s1| * |s2|) time with O(|s2|) space.

Is Count The Repetitions asked at Google/Amazon/Meta?

Count The Repetitions is a classic hard string problem commonly used to test pattern detection and optimization techniques. Variants of subsequence repetition and cycle detection problems have appeared in interviews at large tech companies including Google, Amazon, and Meta.

What data structure is used in Count The Repetitions?

The optimized solution uses a hash map to record previously seen states of the s2 pointer along with counts of processed s1 blocks and matched s2 strings. This allows fast cycle detection and skipping repeated patterns.

What is the time complexity of Count The Repetitions?

The basic simulation approach runs in O(n1 * |s1|) time because it scans s1 repeatedly while matching characters from s2. The optimized cycle detection approach reduces repeated work and runs in approximately O(|s1| * |s2|) time with O(|s2|) additional space.

Comments

Now write it yourselfClose this page and solve Count The Repetitions in the editor, without looking.
Practise Count The Repetitions