aboutsummaryrefslogtreecommitdiff
path: root/count_repititions.py
blob: 320fd0173e8c153c3410d54404212e75d550b620 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 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 strng 's1' can be obtained from string 's2' if we can remove some
characters from 's2' such that it becomes 's1'. 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'
"""


class Solution(object):
    def getMaxRepetitions(self, s1, n1, s2, n2):
        """
        :type s1: str
        :type n1: int
        :type s2: str
        :type n2: int
        :rtype: int
        """
        start = {}
        s1r, s2r, s2_idx = 0, 0, 0
        while s1r < n1:
            s1r += 1
            for ch in s1:
                if ch == s2[s2_idx]:
                    s2_idx += 1
                    if s2_idx == len(s2):
                        s2r += 1
                        s2_idx = 0
            if s2_idx in start:
                prev_s1r, prev_s2r = start[s2_idx]
                circle_s1r, circle_s2r = s1r - prev_s1r, s2r - prev_s2r
                ans = n1 - prev_s1r
                left_s1r = (n1 - prev_s1r) % circle_s1r + prev_s1r
                for key in start:
                    val = start[key]
                    if val[0] == left_s1r:
                        ans += val[1]
                        break
                return ans
            else:
                start[s2_idx] = (s1r, s2r)
        return s2r


if __name__ == "__main__":
    obj = Solution()
    print(obj.getMaxRepetitions(s1="acb", n1=4, s2="ab", n2=2))
    print(obj.getMaxRepetitions(s1="acb", n1=1, s2="acb", n2=1))