diff options
author | Jack Sangdahl <[email protected]> | 2025-05-13 22:54:22 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-13 22:54:22 -0600 |
commit | a4a3dcd62355e55120cb4a4d10d1c2d27c902dff (patch) | |
tree | 268ffee958406dcb20bccd0437bbaac0baba26c9 | |
parent | 246512a2c2bdd6c9bc0380493368834187fa9526 (diff) | |
download | leetcode-a4a3dcd62355e55120cb4a4d10d1c2d27c902dff.tar.gz leetcode-a4a3dcd62355e55120cb4a4d10d1c2d27c902dff.zip |
3337. total characters in string after transformations 2
-rw-r--r-- | total_char_str_transform2.c | 79 | ||||
-rw-r--r-- | total_char_str_transform2.py | 122 |
2 files changed, 201 insertions, 0 deletions
diff --git a/total_char_str_transform2.c b/total_char_str_transform2.c new file mode 100644 index 0000000..3dd1c02 --- /dev/null +++ b/total_char_str_transform2.c @@ -0,0 +1,79 @@ +// 3337. Total Characters in String After Transformations II +#include "leetcode.h" + +/* + * 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. + */ + +const int mod = 1e9 + 7; +typedef long long matrix[26][26]; + +void multiply(const matrix a, const matrix b, matrix res) { + matrix tmp = {{0}}; + for (int i = 0; i < 26; i++) + for (int j = 0; j < 26; j++) { + if (!a[i][j]) + continue; + for (int k = 0; k < 26; k++) + tmp[i][k] = (tmp[i][k] + a[i][j] * b[j][k]) % mod; + } + memcpy(res, tmp, sizeof(tmp)); +} + +void power(const matrix base, int power, matrix res) { + matrix curr, ident = {{0}}; + memcpy(curr, base, sizeof(curr)); + for (int i = 0; i < 26; i++) + ident[i][i] = 1; + while (power > 0) { + if (power & 1) { + matrix tmp; + multiply(ident, curr, tmp); + memcpy(ident, tmp, sizeof(tmp)); + } + matrix sqr; + multiply(curr, curr, sqr); + memcpy(curr, sqr, sizeof(sqr)); + power >>= 1; + } + memcpy(res, ident, sizeof(ident)); +} + +int lengthAfterTransformations(char *s, int t, int *nums, int numsSize) { + (void)numsSize; + long long cnt[26] = {0}; + for (char *i = s; *i; i++) + cnt[*i - 'a']++; + matrix transform = {{0}}; + for (int i = 0; i < 26; i++) + for (int j = 1; j <= nums[i]; j++) + transform[i][(i + j) % 26]++; + matrix pow; + power(transform, t, pow); + int ans = 0; + for (int i = 0; i < 26; i++) { + if (!cnt[i]) + continue; + for (int j = 0; j < 26; j++) + ans = (ans + cnt[i] * pow[i][j]) % mod; + } + return ans; +} + +int main() { + char *s1 = "abcyy", *s2 = "azbk"; + int n1[] = {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}; + int n2[] = {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}; + printf("%d\n", + lengthAfterTransformations(s1, 2, n1, ARRAY_SIZE(n1))); // expect: 7 + printf("%d\n", + lengthAfterTransformations(s2, 1, n2, ARRAY_SIZE(n2))); // expect: 8 +} 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, + ], + ) + ) |