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:
s[i] with the next nums[s[i] - 'a'] consecutive characters in the alphabet. For example, if s[i] = 'a' and nums[0] = 3, the character 'a' transforms into the next 3 consecutive characters ahead of it, which results in "bcd".'z'. For example, if s[i] = 'y' and nums[24] = 3, the character 'y' transforms into the next 3 consecutive characters ahead of it, which results in "zab".Return the length of the resulting string after exactly t transformations.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: 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]
Output: 7
Explanation:
First Transformation (t = 1):
'a' becomes 'b' as nums[0] == 1'b' becomes 'c' as nums[1] == 1'c' becomes 'd' as nums[2] == 1'y' becomes 'z' as nums[24] == 1'y' becomes 'z' as nums[24] == 1"bcdzz"Second Transformation (t = 2):
'b' becomes 'c' as nums[1] == 1'c' becomes 'd' as nums[2] == 1'd' becomes 'e' as nums[3] == 1'z' becomes 'ab' as nums[25] == 2'z' becomes 'ab' as nums[25] == 2"cdeabab"Final Length of the string: The string is "cdeabab", which has 7 characters.
Example 2:
Input: 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]
Output: 8
Explanation:
First Transformation (t = 1):
'a' becomes 'bc' as nums[0] == 2'z' becomes 'ab' as nums[25] == 2'b' becomes 'cd' as nums[1] == 2'k' becomes 'lm' as nums[10] == 2"bcabcdlm"Final Length of the string: The string is "bcabcdlm", which has 8 characters.
Constraints:
1 <= s.length <= 105s consists only of lowercase English letters.1 <= t <= 109nums.length == 261 <= nums[i] <= 25// class Solution {
// public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
// int MOD = 1_000_000_007, len = 0;
// int[] freq = new int[26];
// for (char c : s.toCharArray())
// freq[c - 'a']++;
// while (t-- > 0) {
// int[] transformationArr = new int[26];
// for (int i = 0; i < 26; i++) {
// int next = nums.get(i);
// for (int j = 1; j <= next; j++)
// transformationArr[(i + j) % 26] = (transformationArr[(i + j) % 26] + freq[i]) % MOD;
// }
// freq = transformationArr;
// // System.out.println(Arrays.toString(freq));
// }
// for (int i = 0; i < 26; i++)
// len = (len + freq[i]) % MOD;
// return len;
// }
// }
class Solution {
private static final int MOD = (int) 1e9 + 7;
private static final int L = 26;
private static class Mat {
int[][] a = new int[L][L];
Mat() {}
Mat(Mat copyFrom) {
for (int i = 0; i < L; i++) {
System.arraycopy(copyFrom.a[i], 0, this.a[i], 0, L);
}
}
Mat mul(Mat other) {
Mat result = new Mat();
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
for (int k = 0; k < L; k++) {
result.a[i][j] = (int) ((result.a[i][j] +
(long) this.a[i][k] * other.a[k][j]) %
MOD);
}
}
}
return result;
}
}
/* identity matrix */
private Mat I() {
Mat m = new Mat();
for (int i = 0; i < L; i++) {
m.a[i][i] = 1;
}
return m;
}
/* matrix exponentiation by squaring */
private Mat quickmul(Mat x, int y) {
Mat ans = I();
Mat cur = new Mat(x);
while (y > 0) {
if ((y & 1) == 1) {
ans = ans.mul(cur);
}
cur = cur.mul(cur);
y >>= 1;
}
return ans;
}
// placebo
public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
Mat T = new Mat();
for (int i = 0; i < L; i++) {
for (int j = 1; j <= nums.get(i); j++) {
T.a[(i + j) % L][i] = 1;
}
}
Mat res = quickmul(T, t);
int[] f = new int[L];
for (char ch : s.toCharArray()) {
f[ch - 'a']++;
}
int ans = 0;
for (int i = 0; i < L; i++) {
for (int j = 0; j < L; j++) {
ans = (int) ((ans + (long) res.a[i][j] * f[j]) % MOD);
}
}
return ans;
}
}