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 froms2 = "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 <= 100s1ands2consist 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)
}
Input
s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
Output
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
Input
s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
Output
2