Last updated on October 9th, 2024 at 06:11 pm

Here, We see Count The Repetitions LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Count The Repetitions LeetCode Solution

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

1. Count The Repetitions LeetCode Solution 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;  }
};

2. Count The Repetitions LeetCode Solution 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. Count The Repetitions LeetCode Solution 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));
}

4. Count The Repetitions Solution 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