diff options
Diffstat (limited to 'total_char_str_transform2.py')
-rw-r--r-- | total_char_str_transform2.py | 122 |
1 files changed, 122 insertions, 0 deletions
diff --git a/total_char_str_transform2.py b/total_char_str_transform2.py new file mode 100644 index 0000000..e787077 --- /dev/null +++ b/total_char_str_transform2.py @@ -0,0 +1,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, + ], + ) + ) |