aboutsummaryrefslogtreecommitdiff
path: root/total_char_str_transform2.py
diff options
context:
space:
mode:
Diffstat (limited to 'total_char_str_transform2.py')
-rw-r--r--total_char_str_transform2.py122
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,
+ ],
+ )
+ )