aboutsummaryrefslogtreecommitdiff
path: root/total_char_str_transform2.c
diff options
context:
space:
mode:
Diffstat (limited to 'total_char_str_transform2.c')
-rw-r--r--total_char_str_transform2.c79
1 files changed, 79 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
+}