Last updated on March 2nd, 2025 at 02:35 pm
Here, we see a Count The Repetitions LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Level of Question
Hard
Count The Repetitions LeetCode Solution
Table of Contents
1. Problem Statement
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 froms2 = "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
2. Coding Pattern Used in Solution
The coding pattern used in all the implementations is “Cycle Detection and Optimization”. This pattern involves identifying repetitive cycles in the problem and leveraging them to optimize the solution. The code detects cycles in the alignment of s1 and s2 and uses this information to compute the result efficiently without iterating through all repetitions of s1.
3. Code Implementation in Different Languages
3.1 Count The Repetitions C++
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
vector<int> rapport(102,-1);
vector<int> rest(102,-1);
int b=-1;int posRest=0;int rap=0;
int last=-1;
rapport[0]=rest[0]=0;
for(int i=1;i<=s2.size()+1;i++){
int j;
for(j=0;j<s1.size();j++){
if(s2[posRest]==s1[j]){
posRest++;
if(posRest==s2.size()){
rap++;
posRest=0;
}
}
}
for(int k=0;k<i;k++){
if(posRest==rest[k]){b=k;last=i;break;}
}
rapport[i]=rap;rest[i]=posRest;
if(b>=0)break;
}
int interval=last-b;
if(b>=n1)return rapport[n1]/n2;
return ((n1-b)/interval*(rapport[last]-rapport[b])+rapport[(n1-b)%interval+b])/n2; }
};
3.2 Count The Repetitions Java
class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
int l1 = s1.length(), l2 = s2.length();
int[] next = new int[l2 + 1];
int[] count = new int[l2 + 1];
int cnt = 0, p = 0;
for (int i = 0; i < n1; i++) {
for (int j = 0; j < l1; j++) {
if (s1.charAt(j) == s2.charAt(p)) {
p++;
}
if (p == l2) {
cnt++;
p = 0;
}
}
count[i] = cnt;
next[i] = p;
for (int j = 0; j < i; j++) {
if (next[j] == p) {
int prev_count = count[j];
int pattern_count = (count[i] - count[j]) * ((n1 - j - 1) / (i - j));
int remain_count = count[j + (n1 - j - 1) % (i - j)] - count[j];
return (prev_count + pattern_count + remain_count) / n2;
}
}
}
return count[n1 - 1] / n2;
}
}
3.3 Count The Repetitions JavaScript
var getMaxRepetitions = function(s1, n1, s2, n2) {
let idx2 = 0;
let doWhile = true;
let strCounter = 0;
let sumChars = 0;
let iterations = 0;
while (doWhile && iterations < n1) {
for (let idx1 = 0; idx1 < s1.length; idx1++) {
const char1 = s1[idx1];
const char2 = s2[idx2];
if (char1 === char2) {
sumChars++;
idx2++;
if (sumChars === s2.length) {
strCounter ++;
sumChars = 0;
idx2 = 0;
}
}
}
if (sumChars === 0) {
doWhile = false;
}
iterations++;
}
return Math.floor((strCounter / n2) * (n1 / iterations));
}
3.4 Count The Repetitions Python
class Solution(object):
def getMaxRepetitions(self, s1, n1, s2, n2):
if any(c for c in set(s2) if c not in set(s1)):
return 0
s2_index_to_reps = {0 : (0, 0)}
i, j = 0, 0
s1_reps, s2_reps = 0, 0
while s1_reps < n1:
if s1[i] == s2[j]:
j += 1
i += 1
if j == len(s2):
j = 0
s2_reps += 1
if i == len(s1):
i = 0
s1_reps += 1
if j in s2_index_to_reps:
break
s2_index_to_reps[j] = (s1_reps, s2_reps)
if s1_reps == n1:
return s2_reps // n2
initial_s1_reps, initial_s2_reps = s2_index_to_reps[j]
loop_s1_reps = s1_reps - initial_s1_reps
loop_s2_reps = s2_reps - initial_s2_reps
loops = (n1 - initial_s1_reps) // loop_s1_reps
s2_reps = initial_s2_reps + loops * loop_s2_reps
s1_reps = initial_s1_reps + loops * loop_s1_reps
while s1_reps < n1:
if s1[i] == s2[j]:
j += 1
i += 1
if i == len(s1):
i = 0
s1_reps += 1
if j == len(s2):
j = 0
s2_reps += 1
return s2_reps
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n1 * len(s1)) | O(len(s2)) |
| Java | O(n1 * len(s1)) | O(len(s2)) |
| JavaScript | O(n1 * len(s1)) | O(1) |
| Python | O(n1 * len(s1)) | O(len(s2)) |
- Time Complexity: The time complexity is dominated by the outer loop (up to
n1iterations) and the inner loop (iterating overs1), resulting in O(n1 * len(s1)). - Space Complexity: Space complexity depends on the auxiliary data structures used to store intermediate states for cycle detection. C++, Java, and Python use additional arrays or dictionaries, while JavaScript uses constant space.
- Optimization: The cycle detection significantly reduces the number of iterations required, making the solution efficient for large inputs.