Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Dynamic Programming
"acb" 4 "ab" 2
"acb" 1 "acb" 1
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #466: Count The Repetitions
class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
int m = s1.length(), n = s2.length();
int[][] d = new int[n][0];
for (int i = 0; i < n; ++i) {
int j = i;
int cnt = 0;
for (int k = 0; k < m; ++k) {
if (s1.charAt(k) == s2.charAt(j)) {
if (++j == n) {
j = 0;
++cnt;
}
}
}
d[i] = new int[] {cnt, j};
}
int ans = 0;
for (int j = 0; n1 > 0; --n1) {
ans += d[j][0];
j = d[j][1];
}
return ans / n2;
}
}
// Accepted solution for LeetCode #466: Count The Repetitions
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
}
# Accepted solution for LeetCode #466: Count The Repetitions
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
// Accepted solution for LeetCode #466: Count The Repetitions
/**
* [0466] Count The Repetitions
*
* 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 = "ab<u>dbe</u>c" 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^6
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/count-the-repetitions/
// discuss: https://leetcode.com/problems/count-the-repetitions/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
// Credit: https://leetcode.com/problems/count-the-repetitions/discuss/791499/Rust-translated-8ms-100
pub fn get_max_repetitions(s1: String, n1: i32, s2: String, n2: i32) -> i32 {
if n1 == 0 {
return 0;
};
let mut indices = vec![0; n1 as usize + 1];
let mut counts = vec![0; n1 as usize + 1];
let mut index = 0;
let mut count = 0;
for i in 1..=n1 as usize {
for j in 0..s1.len() {
if s1.as_bytes()[j] == s2.as_bytes()[index] {
index += 1;
}
if index == s2.len() {
index = 0;
count += 1;
}
}
counts[i] = count;
indices[i] = index;
for k in 0..i {
if indices[k] == index {
let pre_count = counts[k];
let pattern_count = (n1 - k as i32) / (i - k) as i32 * (counts[i] - pre_count);
let remain_count = counts[k + (n1 as usize - k) % (i - k)] - pre_count;
return (pre_count + pattern_count + remain_count) / n2;
}
}
}
counts[n1 as usize] / n2
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0466_example_1() {
let s1 = "acb".to_string();
let n1 = 4;
let s2 = "ab".to_string();
let n2 = 2;
let result = 2;
assert_eq!(Solution::get_max_repetitions(s1, n1, s2, n2), result);
}
#[test]
fn test_0466_example_2() {
let s1 = "acb".to_string();
let n1 = 1;
let s2 = "acb".to_string();
let n2 = 1;
let result = 1;
assert_eq!(Solution::get_max_repetitions(s1, n1, s2, n2), result);
}
}
// Accepted solution for LeetCode #466: Count The Repetitions
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);
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.