Count The Repetitions

Problem Id: 466 Difficulty: Hard


Intuition

Solution


class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        mapping = []
        for i in range(len(s2)):
            index = i
            r = 0
            for c in s1:
                if c == s2[index]:
                    index += 1
                if index == len(s2):
                    r += 1
                    index = 0
            mapping.append((index, r))

        n = 0
        index = 0
        j = 0
        while j < n1:
            n += mapping[index][1]
            index = mapping[index][0]
            j += 1
            if index == 0:
                n, j = n * (n1 // j), j * (n1 // j)

        return n // n2