[LeetCode] 每日一题 3335. 字符串转换后的长度 I（模拟法）

题目描述

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

• 如果字符是 'z'，则将其替换为字符串 "ab"。

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

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

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

题目链接

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

示例输入

示例 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

解题思路

这道题一看题面就让我想到用模拟法来解决。整体思路不难，核心在于每次转换时根据规则对字符进行“替换”：

• 普通字符 'a' 到 'y' 向后变一个字母；

• 特殊字符 'z' 会变成两个字符 'a' 和 'b'。

由于最终要求的是第 t 次转换后字符串的长度，而且每一次转换的结果会作为下一次的输入，这就带来一个隐含的问题：前一次更新的字符可能会影响后面还没更新的字符，如果不处理好顺序会出现错误的中间状态。

因此，为了解决这个问题，我采用了一个逆序遍历 + 计数数组的方式。具体步骤如下：

1. 使用一个长度为 26 的数组 count 记录每个字符的数量（count[i] 表示字符 'a' + i 的数量）；

2. 对于每一轮转换：

   • 先记录 'z' 的数量；

   • 然后从 'y' 到 'a' 倒序处理，将当前字符的数量转移到其下一个字符；

   • 最后将 'z' 的数量分别加到 'a' 和 'b' 上，模拟 'z' → "ab"；

3. 所有处理都要记得对 10^9 + 7 取模，防止数值溢出；

4. 最后将所有字符的数量加起来即为最终长度。

这种方法在逻辑上清晰、效率也高，而且避免了每次转换都新建字符串的开销，体现了模拟法在处理规则明确定义的题目中的优势 💡

代码实现

class Solution {
    static final int MOD = 1000000007;

    public int lengthAfterTransformations(String s, int t) {
        long[] count = new long[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        for (int i = 0; i < t; i++) {
            long zCount = count[25];
            count[25] = 0;
            for (int j = 24; j >= 0; j--) {
                count[j + 1] = (count[j + 1] + count[j]) % MOD;
                count[j] = 0;
            }
            count[0] = (count[0] + zCount) % MOD;
            count[1] = (count[1] + zCount) % MOD;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans = (int)((ans + count[i]) % MOD);
        }
        return ans;
    }
}

复杂度分析

• ⏱ 时间复杂度：

  • O(t × 26) = O(t)，每次转换中，我们只需对固定长度的 count 数组进行遍历与更新，因此总体与 t 成正比。

• 🧠 空间复杂度：

  • O(26) = O(1)，只使用一个固定长度的数组来记录字母数量，空间消耗与输入大小无关。

总结

这道题虽然属于模拟题，但细节处理得好坏直接决定了代码的正确性和效率。刚开始我也考虑过直接新建字符串再替换，但那样做不仅效率低，还容易在字符替换顺序上出错。而用计数数组 + 倒序遍历的思路，能避免中间状态干扰，提升效率的同时也让逻辑更加清晰 ✅

这也让我意识到，在处理字符转换类问题时，使用数组记录状态而不是直接操作字符串往往更具优势。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。