What pattern does Total Characters in String After Transformations I follow?

It follows a state transition dynamic programming pattern where character frequencies evolve over t transformations.

Can this approach handle very large t efficiently?

Yes, by tracking frequencies and applying transitions without reconstructing the string, it scales to t up to 10^5.

Why is modulo 10^9 + 7 needed?

The string length can grow exponentially with t, so modulo ensures the result stays within integer limits.

Is it necessary to store the entire string during transformations?

No, storing only character counts is sufficient and prevents memory overflow.

What common mistakes should I avoid in this problem?

Avoid rebuilding the string, forgetting modulo operations, and incorrectly updating character frequencies in transitions.

#3335

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

字符串转换后的长度 I

给你一个字符串 s 和一个整数 t ，表示要执行的转换次数。每次转换需要根据以下规则替换字符串 s 中的每个字符：如果字符是 'z' ，则将其替换为字符串 "ab" 。否则，将其替换为字母表中的下一个字符。例如， 'a' 替换为 'b' ， 'b' 替换为 'c' ，依此类推。返回…

哈希表数学字符串动态规划计数

题目描述

给你一个字符串 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⁵

lightbulb

解题思路

方法一：递推

我们定义 $f[i][j]$ 表示经过 $i$ 次转换后，字母表中第 $j$ 个字母的个数。初始时 $f[0][j]$ 为字符串 $s$ 中字母表中第 $j$ 个字母的个数。

每次转换后，字母表中第 $j$ 个字母的个数可以通过以下方式计算：

\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*}

答案为 $f[t][0] + f[t][1] + \ldots + f[t][25]$ 。

由于答案可能非常大，我们需要对 $10^9 + 7$ 取模。

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	complexity is O(n + t\|Σ\|) where n is the initial string length and \|Σ\| is the alphabet size, since each transformation updates character counts. Space complexity is O(\|Σ\|) for storing frequency counts of all lowercase letters.
空间	O(

psychology

面试官常问的追问

外企场景

question_mark
Notice how naive string reconstruction fails for large t due to exponential growth.
question_mark
Tracking frequencies instead of actual strings is key for optimal performance.
question_mark
State transition dynamic programming is expected; watch for off-by-one or modulo errors.

warning

常见陷阱

外企场景

error
Attempting to build the full string at each transformation, causing memory overflow.
error
Forgetting to apply modulo after each addition, leading to integer overflow.
error
Mismanaging frequency updates and double-counting characters in transitions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual transformed string instead of its length for small t.
arrow_right_alt
Allow custom transformation rules defined per character.
arrow_right_alt
Compute the maximum character frequency after t transformations rather than total length.

help

常见问题

外企场景

继续练习

#3337 字符串转换后的长度 II #3389 使字符频率相等的最少操作次数 #3443 K 次修改后的最大曼哈顿距离