3335. Total Characters in String After Transformations I
Description
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:
- If the character is
'z', replace it with the string"ab". - Otherwise, replace it with the next character in the alphabet. For example,
'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:
- First Transformation (t = 1):
<ul> <li><code>'a'</code> becomes <code>'b'</code></li> <li><code>'b'</code> becomes <code>'c'</code></li> <li><code>'c'</code> becomes <code>'d'</code></li> <li><code>'y'</code> becomes <code>'z'</code></li> <li><code>'y'</code> becomes <code>'z'</code></li> <li>String after the first transformation: <code>"bcdzz"</code></li> </ul> </li> <li><strong>Second Transformation (t = 2)</strong>: <ul> <li><code>'b'</code> becomes <code>'c'</code></li> <li><code>'c'</code> becomes <code>'d'</code></li> <li><code>'d'</code> becomes <code>'e'</code></li> <li><code>'z'</code> becomes <code>"ab"</code></li> <li><code>'z'</code> becomes <code>"ab"</code></li> <li>String after the second transformation: <code>"cdeabab"</code></li> </ul> </li> <li><strong>Final Length of the string</strong>: The string is <code>"cdeabab"</code>, which has 7 characters.</li>
Example 2:
Input: s = "azbk", t = 1
Output: 5
Explanation:
- First Transformation (t = 1):
<ul> <li><code>'a'</code> becomes <code>'b'</code></li> <li><code>'z'</code> becomes <code>"ab"</code></li> <li><code>'b'</code> becomes <code>'c'</code></li> <li><code>'k'</code> becomes <code>'l'</code></li> <li>String after the first transformation: <code>"babcl"</code></li> </ul> </li> <li><strong>Final Length of the string</strong>: The string is <code>"babcl"</code>, which has 5 characters.</li>
Constraints:
1 <= s.length <= 105sconsists only of lowercase English letters.1 <= t <= 105
Solutions
Solution 1: Recurrence
We define $f[i][j]$ to represent the count of the $j$-th letter in the alphabet after $i$ transformations. Initially, $f[0][j]$ is the count of the $j$-th letter in the string $s$.
After each transformation, the count of the $j$-th letter in the alphabet can be calculated as follows:
$$ \begin{align*} f[i][0] &= f[i - 1][25] \ f[i][1] &= f[i - 1][0] + f[i - 1][25] \ f[i][2] &= f[i - 1][1] \ f[i][3] &= f[i - 1][2] \ &\vdots \ f[i][25] &= f[i - 1][24] \end{align*} $$
The answer is $f[t][0] + f[t][1] + \ldots + f[t][25]$.
Since the answer can be very large, we take the result modulo $10^9 + 7$.
The time complexity is $O(t \times |\Sigma|)$, and the space complexity is $O(t \times |\Sigma|)$, where $|\Sigma|$ is the size of the alphabet.
Python3
class Solution:
def lengthAfterTransformations(self, s: str, t: int) -> int:
f = [[0] * 26 for _ in range(t + 1)]
for c in s:
f[0][ord(c) - ord("a")] += 1
for i in range(1, t + 1):
f[i][0] = f[i - 1][25]
f[i][1] = f[i - 1][0] + f[i - 1][25]
for j in range(2, 26):
f[i][j] = f[i - 1][j - 1]
mod = 10**9 + 7
return sum(f[t]) % mod
Java
class Solution {
public int lengthAfterTransformations(String s, int t) {
final int mod = (int) 1e9 + 7;
int[][] f = new int[t + 1][26];
for (char c : s.toCharArray()) {
f[0][c - 'a']++;
}
for (int i = 1; i <= t; ++i) {
f[i][0] = f[i - 1][25] % mod;
f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
for (int j = 2; j < 26; j++) {
f[i][j] = f[i - 1][j - 1] % mod;
}
}
int ans = 0;
for (int j = 0; j < 26; ++j) {
ans = (ans + f[t][j]) % mod;
}
return ans;
}
}
C++
class Solution {
public:
int lengthAfterTransformations(string s, int t) {
const int mod = 1e9 + 7;
vector<vector<int>> f(t + 1, vector<int>(26, 0));
for (char c : s) {
f[0][c - 'a']++;
}
for (int i = 1; i <= t; ++i) {
f[i][0] = f[i - 1][25] % mod;
f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
for (int j = 2; j < 26; ++j) {
f[i][j] = f[i - 1][j - 1] % mod;
}
}
int ans = 0;
for (int j = 0; j < 26; ++j) {
ans = (ans + f[t][j]) % mod;
}
return ans;
}
};
Go
func lengthAfterTransformations(s string, t int) int {
const mod = 1_000_000_007
f := make([][]int, t+1)
for i := range f {
f[i] = make([]int, 26)
}
for _, c := range s {
f[0][c-'a']++
}
for i := 1; i <= t; i++ {
f[i][0] = f[i-1][25] % mod
f[i][1] = (f[i-1][0] + f[i-1][25]) % mod
for j := 2; j < 26; j++ {
f[i][j] = f[i-1][j-1] % mod
}
}
ans := 0
for j := 0; j < 26; j++ {
ans = (ans + f[t][j]) % mod
}
return ans
}
TypeScript
function lengthAfterTransformations(s: string, t: number): number {
const mod = 1_000_000_007;
const f: number[][] = Array.from({ length: t + 1 }, () => Array(26).fill(0));
for (const c of s) {
f[0][c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let i = 1; i <= t; i++) {
f[i][0] = f[i - 1][25] % mod;
f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
for (let j = 2; j < 26; j++) {
f[i][j] = f[i - 1][j - 1] % mod;
}
}
let ans = 0;
for (let j = 0; j < 26; j++) {
ans = (ans + f[t][j]) % mod;
}
return ans;
}