Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

Leetcode Count The Repetitions problem solution

YASH PAL, 31 July 2024

In this Leetcode Count, The Repetitions problem solution 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.

Leetcode Count The Repetitions problem solution

Problem solution in Python.

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        l1 = len(s1)
        l2 = len(s2)
        chars = set(s1)
        for c in s2:
            if c not in chars:
                return 0
        Jumps = []
        def getchar(ofs):
            return s1[ofs%l1]
        for i in range(l1):
            cur = i
            for c in s2:
                while getchar(cur)!=c:
                    cur += 1
                cur += 1
            Jumps.append(cur-i)
        DP = dict()
        def jumplen_pow2(rem, pow2):
            assert(rem>=0 and rem<l1)
            key = (rem, pow2)
            if key in DP:
                return DP[key]
            if pow2==1:
                r = Jumps[rem]
            else:
                pow2 >>= 1
                r = jumplen(rem, pow2)
                r += jumplen((rem+r)%l1, pow2)
            DP[key] = r
            return r
        def jumplen(rem, m):
            if m==0:
                return 0
            pow2 = 1
            jl = 0
            while pow2<=m:
                if pow2&m:
                    l = jumplen_pow2(rem, pow2)
                    jl += l
                    rem = (rem+l)%l1
                pow2 <<= 1
            return jl
        # And we are ready to do the binary search for answer. First we find the borders.
        limit = l1*n1
        m = 1
        prev = 0
        while jumplen_pow2(0,m)<=limit:
            prev = m
            m <<= 1
        l,r = prev,m # the borders
        while r-l>1:
            m = l+(r-l)//2
            if jumplen(0,m)<=limit:
                l = m
            else:
                r = m
        return l//n2

Problem solution in Java.

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int len1 = s1.length(), len2 = s2.length();
        // for detecting cycle
        boolean[] endAt = new boolean[len1];
        char[] chs1 = s1.toCharArray(), chs2 = s2.toCharArray();
        int[] nums1 = new int[len1], nums2 = new int[len1];
        int tltS1Len = len1 * n1;
        int startIdx = s1.indexOf(chs2[0]);
        if(startIdx == -1){
            return 0;
        }
        
        int s2n = 0, s1n = 0, curIdx = 0, prevIdx = -1;
        while(s1n * len1 + curIdx < tltS1Len){
            for(char c : chs2){
                curIdx = s1.indexOf(c, prevIdx + 1);
                
                if(curIdx == -1 && prevIdx == -1){
                    return 0;
                }
                prevIdx = curIdx;
                if(curIdx == -1){
                    ++s1n;
                    curIdx = s1.indexOf(c, prevIdx + 1);
                }
                prevIdx = curIdx;
            }
            // cycle found
            if(endAt[curIdx]){
                break;
            }
            
            prevIdx = curIdx;
            ++s2n;
            endAt[curIdx] = true;
            nums1[curIdx] = s1n;
            nums2[curIdx] = s2n; 
        }
        int cycleLen = (s1n - nums1[curIdx]) * len1;
        if(cycleLen == 0){
            return 0;
        }
        int nS2 = (tltS1Len - startIdx - 1) / cycleLen * s2n;
        int remain = (tltS1Len - startIdx - 1) % cycleLen;
        
        int extraNum = 0;
        for(int i = 0; i < len1; ++i){
            if(!endAt[i]){
                continue;
            }
            
            if(remain >= i + nums1[i] * len1){
                extraNum = Math.max(nums2[i], extraNum);
            }
        }
        return (nS2 + extraNum) / n2;
    }
}

Problem solution in C++.

int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    #define int long long
    const int N = 32;
    vector<vector<int>> dp(N, vector<int>(s2.size()));

    for(int i=0;i<s2.size();i++){
        dp[0][i] = 0;
        for(int j=0;j<s1.size();j++){
            if(s1[j]==s2[(i+dp[0][i])%s2.size()]) dp[0][i]++;
        }
    }

    for(int i=0;i<s2.size();i++){
        cout << dp[0][i] << " ";
    }

    for(int i=1;i<N;i++){
        for(int j=0;j<s2.size();j++){
            dp[i][j] = dp[i-1][j] + dp[i-1][(j+dp[i-1][j])%s2.size()];
        }
    }

    int k = 0;
    int offset = 0;
    for(int i=0;i<N;i++){
        if(n1%2 == 1) {
            int m = dp[i][offset];
            k += m;
            offset = (offset+m)%s2.size();
        }
        n1 /= 2;
    }
    #undef int
    return k/(n2*s2.size());
}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes