点击获取AI摘要

3335. 字符串转换后的长度 I M

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

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

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

由于答案可能非常大，返回其对 10⁹ + 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⁵
s 仅由小写英文字母组成。
1 <= t <= 10⁵

问题分析

对于任意单个字符 c，定义函数

$f(c, t) = \text{在执行 }t\text{ 次转换后，字符 }c\text{ 所对应的最终长度}$

那么对整个字符串 s，最终答案就是

$\sum_{c\in s} f(c, t)\bmod(10^9+7).$

算法思路

状态转移

边界： $f(c,0)=1$ （不变长度为 1）

若 $c\ne \text{'z'}$ ，则每次转换就是下一个字母

$f(c,t) = f(\text{next}(c),\,t-1).$

若 $c=\text{'z'}$ ，则“ z ”展开为 “ab”，对应长度之和

$f(\text{'z'},t) = f(\text{'a'},\,t-1) + f(\text{'b'},\,t-1).$

我们可以对所有 26 个字母维护一个长度-26 的数组 dp，其中dp[i] 表示在当前步剩余转换次数 $k$ 时，字母 char('a'+i) 对应的最终长度。

初始化：dp[i]=1（即 $f(c,0)=1$ ）。

对每一次转换 $k=1$ 到 $t$ ：

对 i=0…24（即 a…y），新的 dp_new[i] = dp[i+1]；
对 i=25（即 z），dp_new[25] = (dp[0] + dp[1]) % MOD。
然后将 dp_new 赋回 dp。

最后，对字符串 s 中每个字符累加对应的 dp[index] 并取模即为答案。

时间复杂度

时间：每步更新 $O(26)$ ，共做 $t$ 步，外加对长度 $|s|$ 的一次遍历，故整体 $O(26\,t + |s|)$ 。

空间：只使用常数大小的长度 26 数组，故 $O(1)$ 。

代码实现

class Solution:
    MOD = 10**9 + 7

    def lengthAfterTransformations(self, s: str, t: int) -> int:
        # dp[i] 表示当前剩余转换次数 k 时，
        # 字符 chr(ord('a')+i) 的最终长度
        dp = [1] * 26

        # 执行 t 次转换
        for _ in range(t):
            dp_new = [0] * 26
            # a..y 直接继承下一个字母
            for i in range(25):
                dp_new[i] = dp[i+1]
            # z -> "ab"
            dp_new[25] = (dp[0] + dp[1]) % self.MOD
            dp = dp_new

        # 累加 s 中每一个字符的贡献
        ans = 0
        base = ord('a')
        for ch in s:
            idx = ord(ch) - base
            ans = (ans + dp[idx]) % self.MOD

        return ans

另看到题解：预处理 + 动态规划（DP） :

状态定义
数组 f 长度为 $26 + \text{MX}$ ，其中前 $0\sim25$ 位初始化为 1（表示任何字母在 0 步转换时长度为 1），后面用来存储更大步数下的长度。

状态转移
对于下标 $i\ge0$ ，f[i+26] = (f[i] + f[i+1]) % \text{MOD}，恰好对应了：

当你对 'z'（在前 26 中的最后一个）做一次转换，它会变成 "ab"，长度就是前面两个状态的和。
而对非 'z' 的字母，其实就是“下一个字母”的长度，也可以映射到同样的数组偏移关系里。

预处理好所有可能的值
因为 $t\le10^5$ ，预先把 f[26] 到 f[26 + 10^5] 都算好，这样每次调用 lengthAfterTransformations(s, t) 时，只要对串中每个字符 $c$ 取 f[t + (ord(c)-ord('a'))]，再累加取模即可。

当 $t$ 接近上限 $10^5$ 时，26*t 约为 $2.6\times10^6$ 次小操作；而打表只做 $10^5$ 次，常数更小，大约快 20× 以上。

且打表后，不管用户输入的 $t$ 是多少（只要 $\le MX$ ），都能直接 $O(1)$ 拿到每个字符的长度贡献。

MOD = 1_000_000_007
ORD_A = ord('a')
MX = 100_000  # t 的最大可能值

# 预处理：f[i] 表示“从某字母出发，剩余 i 步转换后”的长度增量
# 前 26 位对应步数 0，初始化为 1；后面 MX 位存储更大步数时的结果
f = [1] * 26 + [0] * MX
for i in range(MX):
    # 对应状态转移：非 'z' 的字符通过偏移 i+1；'z' 则合并 a、b 两个状态
    f[i + 26] = (f[i] + f[i + 1]) % MOD

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        # 对于每个字符 c，直接通过 f[t + (ord(c)-ORD_A)] 获取剩余 t 步后的长度
        total = 0
        for c in s:
            idx = ord(c) - ORD_A
            total = (total + f[t + idx]) % MOD
        return total