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.

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