Leetcode Count The Repetitions problem solution

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

Topics we are covering

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 solutions