aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-13 22:54:22 -0600
committerJack Sangdahl <[email protected]>2025-05-13 22:54:22 -0600
commita4a3dcd62355e55120cb4a4d10d1c2d27c902dff (patch)
tree268ffee958406dcb20bccd0437bbaac0baba26c9
parent246512a2c2bdd6c9bc0380493368834187fa9526 (diff)
downloadleetcode-a4a3dcd62355e55120cb4a4d10d1c2d27c902dff.tar.gz
leetcode-a4a3dcd62355e55120cb4a4d10d1c2d27c902dff.zip
3337. total characters in string after transformations 2
-rw-r--r--total_char_str_transform2.c79
-rw-r--r--total_char_str_transform2.py122
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,
+ ],
+ )
+ )