Medium

题目描述

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

解题思路

这道题的关键是理解转换规律并优化计算过程。

核心思路分析：

  1. 字符转换规律：除了 'z' 变成 "ab"（长度变为2），其他字符都变成下一个字符（长度保持1）
  2. 频次统计：我们不需要模拟整个字符串转换过程，只需要统计每个字符的出现次数
  3. 动态规划思想：每次转换后，count[i] 表示字符 'a'+i 的数量

转换过程：

  • 字符 'a' 到 'y'：数量直接转移到下一个字符
  • 字符 'z'：分裂成一个 'a' 和一个 'b'

算法步骤：

  1. 统计初始字符串中每个字符的频次
  2. 进行 t 次转换：
    • 对于 'a' 到 'y'，将其数量加到下一个字符上
    • 对于 'z'，将其数量分别加到 'a' 和 'b' 上
  3. 计算最终总长度

优化要点：

  • 使用数组记录每个字符的频次，避免字符串操作
  • 每次转换只需要 O(26) 的时间复杂度
  • 注意取模运算防止溢出

代码实现

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        const int MOD = 1e9 + 7;
        vector<long long> count(26, 0);
        
        // 统计初始字符频次
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // 进行 t 次转换
        for (int i = 0; i < t; i++) {
            vector<long long> newCount(26, 0);
            
            // a-y 转换为下一个字符
            for (int j = 0; j < 25; j++) {
                newCount[j + 1] = (newCount[j + 1] + count[j]) % MOD;
            }
            
            // z 转换为 ab
            newCount[0] = (newCount[0] + count[25]) % MOD; // 'a'
            newCount[1] = (newCount[1] + count[25]) % MOD; // 'b'
            
            count = newCount;
        }
        
        // 计算总长度
        long long result = 0;
        for (int i = 0; i < 26; i++) {
            result = (result + count[i]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        MOD = 10**9 + 7
        count = [0] * 26
        
        # 统计初始字符频次
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        # 进行 t 次转换
        for _ in range(t):
            new_count = [0] * 26
            
            # a-y 转换为下一个字符
            for j in range(25):
                new_count[j + 1] = (new_count[j + 1] + count[j]) % MOD
            
            # z 转换为 ab
            new_count[0] = (new_count[0] + count[25]) % MOD  # 'a'
            new_count[1] = (new_count[1] + count[25]) % MOD  # 'b'
            
            count = new_count
        
        # 计算总长度
        return sum(count) % MOD

public class Solution {
    public int LengthAfterTransformations(string s, int t) {
        const int MOD = 1000000007;
        long[] count = new long[26];
        
        // 统计初始字符频次
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        // 进行 t 次转换
        for (int i = 0; i < t; i++) {
            long[] newCount = new long[26];
            
            // a-y 转换为下一个字符
            for (int j = 0; j < 25; j++) {
                newCount[j + 1] = (newCount[j + 1] + count[j]) % MOD;
            }
            
            // z 转换为 ab
            newCount[0] = (newCount[0] + count[25]) % MOD; // 'a'
            newCount[1] = (newCount[1] + count[25]) % MOD; // 'b'
            
            count = newCount;
        }
        
        // 计算总长度
        long result = 0;
        for (int i = 0; i < 26; i++) {
            result = (result + count[i]) % MOD;
        }
        
        return (int)result;
    }
}

var lengthAfterTransformations = function(s, t) {
    const MOD = 1e9 + 7;
    let count = new Array(26).fill(0);
    
    // 统计初始字符频次
    for (let c of s) {
        count[c.charCodeAt(0) - 97]++;
    }
    
    // 进行 t 次转换
    for (let i = 0; i < t; i++) {
        let newCount = new Array(26).fill(0);
        
        // a-y 转换为下一个字符
        for (let j = 0; j < 25; j++) {
            newCount[j + 1] = (newCount[j + 1] + count[j]) % MOD;
        }
        
        // z 转换为 ab
        newCount[0] = (newCount[0] + count[25]) % MOD; // 'a'
        newCount[1] = (newCount[1] + count[25]) % MOD; // 'b'
        
        count = newCount;
    }
    
    // 计算总长度
    let result = 0;
    for (let i = 0; i < 26; i++) {
        result = (result + count[i]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(26 × t) = O(t)
空间复杂度O(26) = O(1)

说明：

  • 时间复杂度：需要进行 t 次转换，每次转换遍历 26 个字母，因此为 O(26t)
  • 空间复杂度：只使用了固定大小的数组存储字符频次，为 O(26) = O(1)