题目链接3335. 字符串转换后的长度 I - 力扣LeetCode题目描述给你一个字符串s和一个整数t表示要执行的 转换 次数。每次 转换 需要根据以下规则替换字符串s中的每个字符如果字符是z则将其替换为字符串ab。否则将其替换为字母表中的下一个字符。例如a替换为bb替换为c。返回 恰好 执行t次转换后得到的字符串的 长度。由于答案可能非常大返回其对109 7取余的结果。题目示例示例 1 :输入 sabcyy,t2输出7解释 第一次转换(t1)a变为bb变为cc变为dy变为zy变为z第一次转换后的字符串为bcdzz第二次转换(t2)b变为cc变为dd变为ez变为abz变为ab第二次转换后的字符串为cdeabab最终字符串长度字符串为cdeabab长度为7个字符。示例 2 :输入 sazbk,t1输出5解释 第一次转换(t1)a变为bz变为abb变为ck变为l第一次转换后的字符串为babcl最终字符串长度字符串为babcl长度为5个字符。解题思路问题理解给定一个字符串s和变换次数t每次变换的规则是每个字母向后移动一位a→bb→c…y→z。字母z变为a并且每次z变为a时会额外生成一个b。需要计算经过t次变换后字符串的长度。关键思路统计字母频率首先统计字符串中每个字母的出现次数。模拟变换过程每次变换时记录字母z的数量z。将所有字母向后移动一位a→bb→c…y→z。将z变为a即cnt[0] z。由于每个z变为a时会生成一个b因此b的数量增加z。每次变换后字符串长度增加z因为每个z变为a后长度不变但会生成一个b。算法流程初始化字母频率数组cnt。进行t次变换每次变换后更新字母频率和字符串长度。返回最终长度ans。题解代码classSolution{privatefinalintMOD1000000007;// 定义模数防止数值溢出publicintlengthAfterTransformations(Strings,intt){// 统计字符串中每个字母的出现次数int[]cntnewint[26];for(inti0;is.length();i){cnt[s.charAt(i)-a];}intanss.length();// 初始长度为字符串长度// 进行t次变换while(t--0){intzcnt[25];// 记录字母z的数量// 将字母向后移动一位a-b, b-c, ..., y-zfor(inti24;i0;i--){cnt[i1]cnt[i];}cnt[0]z;// 字母z变为acnt[1](cnt[1]z)%MOD;// 字母b的数量增加z因为每个z变为a后会生成一个bans(ansz)%MOD;// 每次变换后字符串长度增加z因为每个z变为a后长度不变但会生成一个b}returnans;}}复杂度分析时间复杂度统计字母频率O(n)其中n是字符串长度。每次变换移动字母频率O(26) O(1)。更新b的数量和字符串长度O(1)。总时间复杂度O(n t * 26) ≈ O(n t)。空间复杂度字母频率数组cntO(26) O(1)。其他变量O(1)。总空间复杂度O(1)。