Count the repetitions

String Dynamic Programming

33.7% acceptance

Jan 13, 2026

446

369

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_max_repetitions(s1: String, n1: i32, s2: String, n2: i32) -> i32 {
    let s1_bytes = s1.as_bytes();
    let s2_bytes = s2.as_bytes();
    let len1 = s1_bytes.len();
    let len2 = s2_bytes.len();

    let mut count1 = 0;
    let mut count2 = 0;
    let mut j = 0;

    let mut recall = vec![(0, 0); len2 + 1];

    while count1 < n1 {
      for i in 0..len1 {
        if s1_bytes[i] == s2_bytes[j] {
          j += 1;
          if j == len2 {
            j = 0;
            count2 += 1;
          }
        }
      }

      count1 += 1;

      if recall[j].0 != 0 {
        let prev_count1 = recall[j].0;
        let prev_count2 = recall[j].1;
        let pattern_count1 = count1 - prev_count1;
        let pattern_count2 = count2 - prev_count2;

        let repeat = (n1 - count1) / pattern_count1;
        count1 += repeat * pattern_count1;
        count2 += repeat * pattern_count2;
      }

      recall[j] = (count1, count2);
    }

    count2 / n2
  }
}