2025-05-26：字符串转换后的长度Ⅱ。用go语言，你有一个只包含小写字母的字符串 s，一个整数 t 表示转换次数，还有一个长度为 26 的数组 nums。每次转换过程如下：

  • 对字符串 s 中的每个字符 s[i]，用字母表中紧跟该字母后面连续的 nums[s[i]-‘a’] 个字符替换它。
  • 超过字母表 ‘z’ 的部分，会从字母表开头重新开始计数（即循环回绕）。

例如，字符 ‘a’ 且对应 nums[0] = 3，则它被替换成 ‘b’、‘c’、‘d’ 三个字母。如果字符是 ‘y’ 且 nums[24] = 3，则替换成 ‘z’、‘a’、‘b’。

经过 t 次这样的转换后，返回最终字符串的长度（结果对 1000000007 取模）。

1 <= s.length <= 100000。

s 仅由小写英文字母组成。

1 <= t <= 1000000000。

nums.length == 26。

1 <= nums[i] <= 25。

输入： s = “abcyy”, t = 2, nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]。

输出： 7。

解释：
第一次转换 (t = 1)

‘a’ 变为 ‘b’ 因为 nums[0] == 1

‘b’ 变为 ‘c’ 因为 nums[1] == 1

‘c’ 变为 ‘d’ 因为 nums[2] == 1

‘y’ 变为 ‘z’ 因为 nums[24] == 1

‘y’ 变为 ‘z’ 因为 nums[24] == 1

第一次转换后的字符串为: “bcdzz”

第二次转换 (t = 2)

‘b’ 变为 ‘c’ 因为 nums[1] == 1

‘c’ 变为 ‘d’ 因为 nums[2] == 1

‘d’ 变为 ‘e’ 因为 nums[3] == 1

‘z’ 变为 ‘ab’ 因为 nums[25] == 2

‘z’ 变为 ‘ab’ 因为 nums[25] == 2

第二次转换后的字符串为: “cdeabab”

字符串最终长度： 字符串为 “cdeabab”，长度为 7 个字符。

题目来自力扣3337。

解题思路

直接模拟每次转换的过程是不可行的，因为 t 可以达到 1e9，而字符串长度可以达到 1e5，时间复杂度会爆炸（O(t * len(s))）。

矩阵快速幂优化：

观察到每次转换中，每个字符的替换是独立的，且替换后的字符数量取决于当前字符和 nums 数组。我们可以用矩阵乘法来表示字符的转换关系：

  • 定义一个 26x26 的转移矩阵 T，其中 T[i][j] 表示字符 j 在转换后对字符 i 的贡献（即字符 j 会被替换为多少个字符 i）。
  • 对于字符 j，它会替换为 nums[j] 个连续字符，分别是 (j+1)%26, (j+2)%26, …, (j+nums[j])%26。
  • 因此，T[(j+k)%26][j] = 1，其中 k 从 1 到 nums[j]。
  • 初始时，统计字符串 s 中每个字符的频率 f（f[i] 表示字符 'a'+i 的出现次数）。
  • 经过 t 次转换后，字符的频率向量 f_t 可以通过矩阵快速幂计算：f_t = T^t * f。
  • 最终字符串的长度是 f_t 中所有元素的和。

具体步骤：

  1. 构建转移矩阵 T：
  • 对于每个字符 j（0 到 25），遍历 k 从 1 到 nums[j]，设置 T[(j+k)%26][j] = 1。
  • 这样，T[i][j] 表示字符 j 在转换后会贡献多少个字符 i。
  1. 初始频率 f：
  • 统计 s 中每个字符的出现次数。
  1. 计算 T^t：
  • 使用矩阵快速幂高效计算 T 的 t 次幂。
  1. 计算 f_t = T^t * f：
  • 矩阵乘法计算新的频率向量。
  1. 求和：
  • f_t 中所有元素的和就是最终字符串的长度。

时间复杂度和空间复杂度

  • 时间复杂度：
  • 构建转移矩阵 T：O(26 * max(nums)) ≈ O(26 * 25) = O(650)。
  • 矩阵快速幂：每次矩阵乘法是 O(26^3) = O(17576)，共 O(log t) 次，因此是 O(17576 * log t)。
  • 计算 f_t：矩阵乘向量是 O(26^2) = O(676)。
  • 总时间复杂度：O(650 + 17576 * log t + 676) ≈ O(log t)（因为 26^3 是常数）。
  • 空间复杂度：
  • 转移矩阵 T 和中间矩阵：O(26^2) = O(676)。
  • 频率向量：O(26)。
  • 总空间复杂度：O(1)（常数空间，与输入规模无关）。

总结

通过矩阵快速幂，我们将问题从 O(t * len(s)) 优化到 O(log t) 的时间复杂度，能够高效处理 t 很大的情况。空间复杂度是常数 O(1)。

Go完整代码如下：

package mainimport ("fmt"
)const MOD = 1e9 + 7
const L = 26func lengthAfterTransformations(s string, t int, nums []int) int {T := NewMat()for i := 0; i < L; i++ {for j := 1; j <= nums[i]; j++ {T.a[(i+j)%L][i] = 1}}res := quickMul(T, t)f := make([]int, L)for _, ch := range s {f[ch-'a']++}ans := 0for i := 0; i < L; i++ {for j := 0; j < L; j++ {ans = (ans + res.a[i][j]*f[j]) % MOD}}return ans
}type Mat struct {a [L][L]int
}func NewMat() *Mat {return &Mat{}
}func NewMatCopy(from *Mat) *Mat {m := &Mat{}for i := 0; i < L; i++ {for j := 0; j < L; j++ {m.a[i][j] = from.a[i][j]}}return m
}func (m *Mat) Mul(other *Mat) *Mat {result := NewMat()for i := 0; i < L; i++ {for j := 0; j < L; j++ {for k := 0; k < L; k++ {result.a[i][j] = (result.a[i][j] + m.a[i][k]*other.a[k][j]) % MOD}}}return result
}/* 单位矩阵 */
func I() *Mat {m := NewMat()for i := 0; i < L; i++ {m.a[i][i] = 1}return m
}/* 矩阵快速幂 */
func quickMul(x *Mat, y int) *Mat {ans := I()cur := NewMatCopy(x)for y > 0 {if y&1 == 1 {ans = ans.Mul(cur)}cur = cur.Mul(cur)y >>= 1}return ans
}func main() {s := "abcyy"t := 2nums := []int{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}result := lengthAfterTransformations(s, t, nums)fmt.Println(result)
}

2025-05-26：字符串转换后的长度Ⅱ。用go语言，你有一个只包含小写字母的字符串 s，一个整数 t 表示转换次数，还有一个长度为 26 的数组 nums。每次转换过程如下： - 对字符串 s 中_开发语言

Rust完整代码如下：

const MOD: i64 = 1_000_000_007;
const L: usize = 26;type Mat = [[i64; L]; L];fn new_mat() -> Mat {[[0; L]; L]
}fn identity() -> Mat {let mut m = new_mat();for i in 0..L {m[i][i] = 1;}m
}fn mat_mul(a: &Mat, b: &Mat) -> Mat {let mut res = new_mat();for i in 0..L {for j in 0..L {let mut sum = 0;for k in 0..L {sum += a[i][k] * b[k][j];}res[i][j] = sum % MOD;}}res
}fn mat_pow(mut base: Mat, mut exp: i64) -> Mat {let mut result = identity();while exp > 0 {if exp & 1 == 1 {result = mat_mul(&result, &base);}base = mat_mul(&base, &base);exp >>= 1;}result
}fn length_after_transformations(s: &str, t: i64, nums: &[i32]) -> i64 {// 构造转换矩阵 T，T[i][j] = 1 表示从 j 变成 i 的可能路径let mut T = new_mat();for i in 0..L {for j in 1..=nums[i] {let to = (i + j as usize) % L;T[to][i] = 1;}}// 矩阵快速幂计算 T^tlet res = mat_pow(T, t);// 统计初始字符串中各字母的数量let mut f = [0i64; L];for b in s.bytes() {f[(b - b'a') as usize] += 1;}// 计算最终长度 = ∑_(i,j) res[i][j] * f[j]let mut ans = 0i64;for i in 0..L {for j in 0..L {ans = (ans + res[i][j] * f[j]) % MOD;}}ans
}fn main() {let s = "abcyy";let t = 2;let nums = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,];let result = length_after_transformations(s, t, &nums);println!("{}", result);
}

2025-05-26：字符串转换后的长度Ⅱ。用go语言，你有一个只包含小写字母的字符串 s，一个整数 t 表示转换次数，还有一个长度为 26 的数组 nums。每次转换过程如下： - 对字符串 s 中_开发语言_02