aboutsummaryrefslogtreecommitdiff
path: root/total_char_str_transform2.py
blob: e787077bc71d26dc955f00eddff2b03e4a956f35 (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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
# 3337. Total Characters in String After Transformations II

"""
you are given a string 's' consisting of lowercase english letters, an
integer 't' representing the number of transformations to perform, and an
array 'nums' of size 26. in one transformation, every character in 's' is
replaced according to the following rules: replace 's[i]' with the next
'nums[s[i] - 'a']' consecutive characters in the alphabet. the transformation
wraps around the alphabet if it exceeds 'z'. return the length of the
resulting string after exactly 't' tranformations.
"""


class Solution(object):
    def multiply(self, a, b, mod):
        res = [[0] * len(b[0]) for _ in range(len(a))]
        for i in range(len(a)):
            for j in range(len(b[0])):
                for k in range(len(b)):
                    res[i][j] += a[i][k] * b[k][j]
                res[i][j] %= mod
        return res

    def power(self, base, pow, mod):
        n = len(base)
        res = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
        while pow > 0:
            if pow & 1:
                res = self.multiply(res, base, mod)
            base = self.multiply(base, base, mod)
            pow >>= 1
        return res

    def lengthAfterTransformations(self, s, t, nums):
        """
        :type s: str
        :type t: int
        :type nums: List[int]
        :rtype: int
        """
        transform = [[0] * 26 for i in range(26)]
        for i, j in enumerate(nums):
            for k in range(i + 1, i + j + 1):
                transform[i][k % 26] = 1
        cnt, mod = [0] * 26, 10**9 + 7
        matrix = self.power(transform, t, mod)
        for i in s:
            cnt[ord(i) - ord("a")] += 1
        ans = self.multiply([cnt], matrix, mod)
        return sum(ans[0]) % mod


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.lengthAfterTransformations(
            s="abcyy",
            t=2,
            nums=[
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                1,
                2,
            ],
        )
    )
    print(
        obj.lengthAfterTransformations(
            s="azbk",
            t=1,
            nums=[
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
                2,
            ],
        )
    )