You are given a string s and an integer t, representing the number of transformations to perform. In one transformation, every character in s is replaced according to the following rules:
'z', replace it with the string "ab".'a' is replaced with 'b', 'b' is replaced with 'c', and so on.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
Output: 7
Explanation:
'a' becomes 'b''b' becomes 'c''c' becomes 'd''y' becomes 'z''y' becomes 'z'"bcdzz"'b' becomes 'c''c' becomes 'd''d' becomes 'e''z' becomes "ab"'z' becomes "ab""cdeabab""cdeabab", which has 7 characters.Example 2:
Input: s = "azbk", t = 1
Output: 5
Explanation:
'a' becomes 'b''z' becomes "ab"'b' becomes 'c''k' becomes 'l'"babcl""babcl", which has 5 characters.
Constraints:
1 <= s.length <= 105s consists only of lowercase English letters.1 <= t <= 105class Solution {
public int lengthAfterTransformations(String s, int t) {
int[] freq = new int[26];
for (char c : s.toCharArray())
freq[c - 'a']++;
int MOD = 1_000_000_007, len = s.length(), Zs = 25, Bs = 0;
// idx ptrs for chars Z and B (B=0 bcz prev A contributes to B, prev B contributes to C instead)
for (int i = 0; i < t; i++) {
len = (len + freq[Zs]) % MOD;
freq[Bs] = (freq[Bs] + freq[Zs]) % MOD; // so init with freq('a'), then add 'z' contribution
Zs = (26 + Zs - 1) % 26; // left shift Z ptr circularly, to simulate A->B, B->C & so on.
Bs = (Zs + 1) % 26; // the char right after Z contributes to B
}
return len;
}
}class Solution {
public int lengthAfterTransformations(String s, int t) {
int MOD = 1_000_000_007;
long[] freq = new long[26];
for (char c : s.toCharArray())
freq[c - 'a']++;
while (t-- > 0) {
long temp = freq[25];
freq[25] = 0;
for (int i = 24; i >= 0; i--) {
freq[i + 1] = freq[i];
freq[i] = 0;
}
freq[0] = temp;
freq[1] = (freq[1] + temp) % MOD;
}
long len = 0;
for (long f : freq)
len = (len + f) % MOD;
return (int) len;
}
}class Solution {
public int lengthAfterTransformations(String s, int t) {
int MOD = 1_000_000_007;
long len = s.length();
long[] freq = new long[26];
for (char c : s.toCharArray())
freq[c - 'a']++;
int Zs = 25, Bs = 0;
for (int i = 0; i < t; i++) {
len = (len + freq[Zs]) % MOD;
freq[Bs] = (freq[Bs] + freq[Zs]) % MOD;
Zs = (26 + Zs - 1) % 26;
Bs = (Zs + 1) % 26;
}
return (int) len;
}
}