## Algorithm

Problem Name: 466. Count The Repetitions

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

Constraints:

• `1 <= s1.length, s2.length <= 100`
• `s1` and `s2` consist of lowercase English letters.
• `1 <= n1, n2 <= 106`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const getMaxRepetitions = function(s1, n1, s2, n2) {
let j = 0,
i,
count = 0,
perCycle = 0,
firstEnd = -1,
lastEnd = -1,
nonMatch = 0
for (i = 0; i  <  s1.length * n1; i++) {
if (s2[j] === s1[i % s1.length]) {
j++
nonMatch = 0
} else if (++nonMatch >= s1.length) break
if (j === s2.length) {
count++
perCycle++
j = 0
if (lastEnd !== -1) continue
else if (firstEnd === -1) {
firstEnd = i
perCycle = 0
} else if ((i - firstEnd) % s1.length === 0) {
let cycleLen = i - firstEnd
let remainLen = s1.length * n1 - i - 1
let cycles = Math.floor(remainLen / cycleLen)
count += cycles * perCycle
i += cycles * cycleLen
}
}
}
return Math.floor(count / n2)
}
``````
Copy The Code &

Input

cmd
s1 = "acb", n1 = 4, s2 = "ab", n2 = 2

Output

cmd
2

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution(object):
def getMaxRepetitions(self, s1, n1, s2, n2):
start = {} # s2_idx : s1_round, s2_round
s1_round, s2_round, s2_idx = 0, 0, 0
while s1_round < n1:
s1_round += 1
for ch in s1:
if ch == s2[s2_idx]:
s2_idx += 1
if s2_idx == len(s2):
s2_round += 1
s2_idx = 0
if s2_idx in start:
prev_s1_round, prev_s2_round = start[s2_idx]
circle_s1_round, circle_s2_round = s1_round - prev_s1_round, s2_round - prev_s2_round
res = (n1 - prev_s1_round) // circle_s1_round * circle_s2_round
left_s1_round = (n1 - prev_s1_round) % circle_s1_round + prev_s1_round
for key, val in start.items():
if val[0] == left_s1_round:
res += val[1]
break
return res // n2
else:
start[s2_idx] = (s1_round, s2_round)
return s2_round // n2
``````
Copy The Code &

Input

cmd
s1 = "acb", n1 = 4, s2 = "ab", n2 = 2

Output

cmd
2
Advertisements