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.
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()); }