# Python solution by finding cycle

• We match string `s1*n1` and multiple `s2` in a greedy way, trying to find a cycle. Here a cycle means that when we match `s2` `k` times and `k + cycle_length` times, the last characters in both cases match to the characters of the same index in `s1`.
Then `s1*n1` can be decomposed into three parts: the part before the cycle, cycle part, the remaining incomplete cycle part.
The greediness of the our matching procedure guarantee that the number of `s2` matched in the first part and last part is the same as the one we would get if these two parts are concatenated, which will be a multiple of `s1`.

``````class Solution(object):
def getMaxRepetitions(self, s1, n1, s2, n2):
set_s1, set_s2 = set(s1), set(s2)
if not all(ch in set_s1 for ch in s2):
return 0
s1 = ''.join(ch for ch in s1 if ch in set_s2) # get rid of redundant character in s1.'
tmap = dict()
# tmap[i] = k means that at the first time s1[i] matchs to the last character in s2, we have matched s2 k times in total.
record = [0]
# record[i] = k means that k is the smallest number such that s2*i is a subsequence of s1*k.
cnt1 = 0
beg = 0
while True:
for ch in s2:
i = s1.find(ch, beg)
if i == -1:
cnt1 += 1
i = s1.find(ch)
beg = i+1
record.append(cnt1 + 1)
if record[-1] > n1:
return (len(record)-2)//n2
if i in tmap: # when find a full cycle, exit the loop.
break
else:
tmap[i] = len(record)-1
'''
cycle_beg denotes the number of times we have scanned s1 (including the current one) when the cycle begins.
cycle_s1 denotes the number of s1 in a full cycle.
cycle_s2 denotes the number of s2 in a full cycle.
'''
cycle_beg = record[tmap[i]]
cycle_s1 = cnt1+1 - cycle_beg
cycle_s2 = len(record)-1 - tmap[i]
d, r = divmod(n1 - cycle_beg, cycle_s1)
# d denotes the number of full cycles, r denotes the remaining number of s1 in the last incomplete cycle.
remain = cycle_beg + r # concatenate the part before the cycle begins and the incomplete cycle remaining.
j = 0
while record[j] <= remain: # record[-1] > remain is yet to be proved.
j += 1
cnt = cycle_s2*d + j-1
return cnt//n2
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.