题目描述

给你一个字符串 s 和一个整数 t，表示要执行的 转换 次数。每次 转换 需要根据以下规则替换字符串 s 中的每个字符：

• 如果字符是 'z'，则将其替换为字符串 "ab"。
• 否则，将其替换为字母表中的下一个字符。例如，'a' 替换为 'b'，'b' 替换为 'c'，依此类推。

返回 恰好 执行 t 次转换后得到的字符串的 长度。

由于答案可能非常大，返回其对 10^9 + 7 取余的结果。

样例

输入： s = "abcyy", t = 2

输出： 7

解释：

第一次转换 (t = 1)
'a' 变为 'b'
'b' 变为 'c'
'c' 变为 'd'
'y' 变为 'z'
'y' 变为 'z'
第一次转换后的字符串为："bcdzz"
第二次转换 (t = 2)
'b' 变为 'c'
'c' 变为 'd'
'd' 变为 'e'
'z' 变为 "ab"
'z' 变为 "ab"
第二次转换后的字符串为："cdeabab"
最终字符串长度：字符串为 "cdeabab"，长度为 7 个字符。

输入： s = "azbk", t = 1

输出： 5

解释：

第一次转换 (t = 1)
'a' 变为 'b'
'z' 变为 "ab"
'b' 变为 'c'
'k' 变为 'l'
第一次转换后的字符串为："babcl"
最终字符串长度：字符串为 "babcl"，长度为 5 个字符。

限制

• 1 <= s.length <= 10^5
• s 仅由小写英文字母组成。
• 1 <= t <= 10^5

算法

(模拟) $O(n + t |\Sigma|)$

1. 预处理求出每个字符的出现次数。
2. 对于每一次操作，遍历所有的字符，并令当前字符的数量等于前一个字符的数量。对于字符 $z$ 特殊处理。
3. 最后累加所有字符的出现次数。

时间复杂度

• 预处理的时间复杂度为 $O(n + |\Sigma|)$。
• 每次操作的时间复杂度为 $O(|\Sigma|)$。
• 故总时间复杂度为 $O(n + t |\Sigma|)$。

空间复杂度

• 需要 $O(|\Sigma|)$ 的额外空间存储字符的出现次数。

C++ 代码

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        const int mod = 1000000007;

        vector<int> cnt(26, 0);
        for (char c : s)
            ++cnt[c - 'a'];

        while (t--) {
            int z = cnt.back();
            for (int i = 25; i >= 1; i--)
                cnt[i] = cnt[i - 1];

            cnt[0] = z;
            cnt[1] = (cnt[1] + z) % mod;
        }

        int ans = 0;
        for (int v : cnt)
            ans = (ans + v) % mod;

        return ans;
    }
};