M3335.字符串转换后的长度I

implementation, https://leetcode.cn/problems/total-characters-in-string-after-transformations-i/

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

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

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

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

示例 1：

输入： 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 个字符。

示例 2：

输入： 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

需要解决的问题是：在对字符串 s 进行 t 次转换后，计算最终字符串的长度。由于每次转换可能导致字符变为两个字符（如 'z' → "ab"），所以直接模拟转换过程会非常低效，尤其是当 t 很大时。

🔍 解题思路

我们可以使用 动态规划 或 数学递推 的方式来避免实际构造字符串。我们只关心每个字符在 t 次转换后会产生多少个字符。

🧠 观察规律：

对于任意字符 ch != 'z'：
- 每次转换只是变成下一个字符，不会导致数量变化。
- 直到它变成 'z' 为止，之后就会分裂成 "ab"（即 2 个字符）。
所以可以预计算出一个字符经过 0~t 次变换后，会变成什么字符，并记录它的“生成字符数”。
更聪明的做法是，为每个字符 'a' 到 'z' 预处理它在 t 次转换后的贡献长度。

✅ 动态规划方法

设 dp[c][k] 表示字符 c 经过 k 次转换后的字符数量：

如果当前字符不是 'z'，则它下一轮变成下一个字符；
如果是 'z'，则变成 "ab"，也就是分别递归处理 'a' 和 'b'。

因此可以使用记忆化递归或动态规划来计算每个字符在 t 轮变换中的总长度贡献。

🧮 数学优化

也可以从另一个角度思考：对于字符 'a' 到 'y'，它们在没有变成 'z' 前只会线性递增；而一旦变成 'z'，就会分裂为 2 个字符。

所以可以预处理出：

每个字符在 t 轮中变成 'z' 的次数；
然后统计这些 'z' 又能产生多少个新字符。

但更简单的是用 模拟能量传播 的方式：

✅ 最终解法：模拟字符演化 + 模运算

定义一个数组 cnt[26]，其中 cnt[i] 表示当前第 i 轮字符的数量。

初始时统计字符串 s 中每个字符出现的次数；
每轮更新 cnt 数组：
- 每个字符向右移动一位；
- 'z' 变成 "ab"，即 cnt[0] += cnt[25], cnt[1] += cnt[25]

因为每轮操作是确定性的，我们只需模拟 t 次即可。

✅ Python 实现代码如下：

python

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        MOD = 10**9 + 7
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1
        
        for _ in range(t):
            new_cnt = [0] * 26
            # 处理 a ~ y
            for i in range(25):
                new_cnt[i + 1] = (new_cnt[i + 1] + cnt[i]) % MOD
            # 处理 z -> ab
            new_cnt[0] = (new_cnt[0] + cnt[25]) % MOD
            new_cnt[1] = (new_cnt[1] + cnt[25]) % MOD
            cnt = new_cnt
        
        return sum(cnt) % MOD

⏱️ 时间复杂度分析

初始化计数：O(n)
模拟 t 次转换：O(t * 26)
总体复杂度：O(n + t * 26)，适用于 n,t <= 1e5

M3335.字符串转换后的长度I ​

M3335.字符串转换后的长度I