{x}
blog image

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

Solution Explanation: Count The Repetitions

This problem asks to find the maximum integer m such that str2 repeated m times (str2 concatenated m times) can be obtained by removing some characters from str1 (s1 concatenated n1 times).

The solution uses a preprocessing step followed by iteration. The core idea is to avoid redundant computations by pre-calculating how many times s2 can be obtained from s1 starting at different positions in s2.

Preprocessing:

The code first creates a 2D array (or dictionary in Python) d of size len(s2). Each entry d[i] stores a pair:

  • d[i][0] (or d[i][0] in Python): The number of times s2 is fully contained in s1 when starting the matching process at position i in s2.
  • d[i][1] (or d[i] in Python): The index of the next character in s2 that needs to be matched after a full match of s1. This represents the remaining unmatched portion of s2 after one iteration.

The preprocessing loop iterates through each starting position i in s2. For each i, it simulates matching s1 against s2 starting from index i. It counts how many complete repetitions of s2 are found (cnt) and tracks the index j in s2 after matching all of s1. This pair (cnt, j) is then stored in d[i].

Iteration and Calculation:

After preprocessing, the code initializes a variable ans (the total count of s2 repetitions found in str1) to 0 and an index j to 0 (starting from the beginning of s2). Then, it iterates n1 times, simulating concatenating s1 repeatedly. In each iteration:

  1. It adds the pre-computed count d[j][0] to ans. This is the number of s2 repetitions found when starting at index j.
  2. It updates j to d[j][1]. This represents moving to the next unmatched portion of s2 for the next iteration.

Finally, the code divides ans by n2 to get the maximum number of complete repetitions of str2 that can be obtained from str1, obtaining the final result m. The floor division (// in Python or Math.floor in TypeScript) is essential because we're interested in the maximum integer m.

Time and Space Complexity:

  • Time Complexity: O(mn + n1), where m is the length of s1, n is the length of s2, and n1 is the number of times s1 is repeated. The preprocessing step takes O(mn) time, and the iteration takes O(n1) time.
  • Space Complexity: O(n), The space used is dominated by the d array which has size proportional to the length of s2.

The optimization comes from the preprocessing step. Without it, the algorithm would have to repeatedly match s1 against s2, leading to significantly higher complexity. The preprocessing step effectively memoizes the results of these matches, enabling efficient calculation of the final answer.