3335.字符串转换后的长度 I：I先递推

【LetMeFly】3335.字符串转换后的长度 I：I先递推

力扣题目链接：https://leetcode.cn/problems/total-characters-in-string-after-transformations-i/

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

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

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

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

 

示例 1：

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

输出： 7

解释：

• 第一次转换 (t = 1)

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

示例 2：

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

输出： 5

解释：

• 第一次转换 (t = 1)

  <ul>
  	<li><code>'a'</code> 变为 <code>'b'</code></li>
  	<li><code>'z'</code> 变为 <code>"ab"</code></li>
  	<li><code>'b'</code> 变为 <code>'c'</code></li>
  	<li><code>'k'</code> 变为 <code>'l'</code></li>
  	<li>第一次转换后的字符串为：<code>"babcl"</code></li>
  </ul>
  </li>
  <li><strong>最终字符串长度</strong>：字符串为 <code>"babcl"</code>，长度为 5 个字符。</li>
  

 

提示：

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

解题方法：递推

使用一个长为26的数组记录每个字符当前分别有多少次。

然后进行$t$次模拟：

首先记下z的出现次数；

接着从y到a遍历，将cnt[i]赋值给cnt[i + 1]；

最后令cnt[0] := z，cnt[1] += z，ans += z（这是因为没轮操作z会变成ab，同时字符串长度会加一）

• 时间复杂度$O(len(s)\cdot C)$，其中$C=26$
• 空间复杂度$O(C)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-05-13 09:02:15
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-13 09:15:09
 * @Description: 3335: AC,92.65%,98.53%
 */
const int MOD = 1e9 + 7;

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        int cnt[26] = {0};
        for (char c : s) {
            cnt[c - 'a']++;
        }
        int ans = s.size();
        while (t--) {
            int z = cnt[25];
            for (int i = 24; i >= 0; i--) {  // 这里必须从后往前
                cnt[i + 1] = cnt[i];
            }
            cnt[0] = z;
            cnt[1] = (cnt[1] + z) % MOD;
            ans = (ans + z) % MOD;
            // debug(cnt);
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-05-13 09:02:15
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-13 09:18:14
'''
MOD = 1000000007

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - 97] += 1
        ans = len(s)
        for _ in range(t):
            z = cnt[-1]
            for i in range(24, -1, -1):
                cnt[i + 1] = cnt[i]
            cnt[0] = z
            cnt[1] = (cnt[1] + z) % MOD
            ans = (ans + z) % MOD
        return ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-05-13 09:02:15
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-13 09:19:43
 */

class Solution {
    private final int MOD = 1000000007;

    public int lengthAfterTransformations(String s, int t) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        int ans = s.length();
        while (t-- > 0) {
            int z = cnt[25];
            for (int i = 24; i >= 0; i--) {
                cnt[i + 1] = cnt[i];
            }
            cnt[0] = z;
            cnt[1] = (cnt[1] + z) % MOD;
            ans = (ans + z) % MOD;
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-05-13 09:02:15
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-13 09:28:34
 */
package main

var MOD3351 = 1000000007

func lengthAfterTransformations(s string, t int) int {
    cnt := make([]int, 26)
    for i := 0; i < len(s); i++ {
        cnt[s[i] - 'a']++
    }
    ans := len(s)
    for i := 0; i < t; i++ {
        z := cnt[25]
        for j := 24; j >= 0; j-- {
            cnt[j + 1] = cnt[j]
        }
        cnt[0] = z
        cnt[1] = (cnt[1] + z) % MOD3351
        ans = (ans + z) % MOD3351
    }
    return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源