点击获取AI摘要

3337. 字符串转换后的长度 II H

给你一个由小写英文字母组成的字符串 s，一个整数 t 表示要执行的转换次数，以及一个长度为 26 的数组 nums。每次转换需要根据以下规则替换字符串 s 中的每个字符：

将 s[i] 替换为字母表中后续的 nums[s[i] - 'a'] 个连续字符。例如，如果 s[i] = 'a' 且 nums[0] = 3，则字符 'a' 转换为它后面的 3 个连续字符，结果为 "bcd"。
如果转换超过了 'z'，则回绕到字母表的开头。例如，如果 s[i] = 'y' 且 nums[24] = 3，则字符 'y' 转换为它后面的 3 个连续字符，结果为 "zab"。

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

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

示例 1：

输入： 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 个字符。

示例 2：

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

输出： 8

解释：

第一次转换 (t = 1)

'a' 变为 'bc' 因为 nums[0] == 2

'z' 变为 'ab' 因为 nums[25] == 2

'b' 变为 'cd' 因为 nums[1] == 2

'k' 变为 'lm' 因为 nums[10] == 2

第一次转换后的字符串为: "bcabcdlm"

字符串最终长度： 字符串为 "bcabcdlm"，长度为 8 个字符。

提示：

1 <= s.length <= 10⁵
s 仅由小写英文字母组成。
1 <= t <= 109
nums.length == 26
1 <= nums[i] <= 25

问题分析

输入字符串 s 长度可达 10⁵；
转换次数 t 可达 10⁹；
每个字符在一次转换中根据 nums 数组映射到一定数量的后续字符；
最终字符串长度需要对 10⁹+7 取余。

算法思路

直接模拟每次转换会导致指数级爆炸，根本不能在时间和空间上承受；

需要一个常量级（与 $t$ 无关）或对数级（ $\log t$ ）的方法来计算最终长度。

将字符的「长度增长」看作状态转移：定义 $f(i, k)$ 为从字符 $i$ （0 对应 ‘a’, …, 25 对应 ‘z’）经过 $k$ 次转换后产生的字符串长度，则有递推

$f(i, 0) = 1 \\ f(i, k) = \sum_{j=1}^{\text{nums}[i]} f((i+j) \mod 26, k-1)$

用矩阵乘法表示一次转换：构造 $26 \times 26$ 矩阵 $M$ ， $M[i][j]$ 表示从字符 i 到字符 j 的贡献次数；

那么状态向量

$\mathbf{v}_k = \begin{bmatrix} f(0, k) \\ f(1, k) \\ \vdots \\ f(25, k) \end{bmatrix}$

满足

$\mathbf{v}_0 = \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{bmatrix} \\ \mathbf{v}_k = M \cdot \mathbf{v}_{k-1} \\ \Rightarrow \mathbf{v}_t = M^t \cdot \mathbf{v}_0$

预处理初始字符串中各字符的出现次数 $\text{cnt}[0 \ldots 25]$ ；最终答案

$\text{ans} = \sum_{i=0}^{25} \text{cnt}[i] \cdot f(i, t) \mod (10^9 + 7) \\ = \mathbf{cnt}^T \cdot \mathbf{v}_t \mod (10^9 + 7)$

时间复杂度

用 矩阵快速幂 在 $O(26^3 \cdot \log t)$ 时间内计算 $M^t$ ，再做 $O(26^2)$ 的乘法，整体可在毫秒级完成。

构造矩阵： $O(26 \cdot \max(\text{nums}[i])) \leq O(26^2)$ ；

矩阵快速幂： $O(26^3 \cdot \log t)$ ；

最终向量点乘： $O(26) + O(|s|)$ ；

总体： $O(26^3 \cdot \log t + |s|)$ ，对 $|s|$ 和 $t$ 均很高的场景都能胜任。

代码实现

class Solution:
    def lengthAfterTransformations(self, s: str, t: int, nums: list[int]) -> int:
        MOD = 10**9 + 7

        # —— 中间变量：将输入存入 brivlento 以备后续使用 —— 
        brivlento = (s, t, nums)

        # 1. 构造 26×26 状态转移矩阵 M
        M = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for step in range(1, nums[i] + 1):
                j = (i + step) % 26
                M[i][j] += 1

        # 2. 矩阵乘法与幂运算
        def mat_mul(A, B):
            size = 26
            C = [[0]*size for _ in range(size)]
            for i in range(size):
                for k in range(size):
                    if A[i][k]:
                        aik = A[i][k]
                        for j in range(size):
                            C[i][j] = (C[i][j] + aik * B[k][j]) % MOD
            return C

        def mat_pow(mat, power):
            # 单位矩阵
            size = 26
            R = [[1 if i==j else 0 for j in range(size)] for i in range(size)]
            base = mat
            while power > 0:
                if power & 1:
                    R = mat_mul(R, base)
                base = mat_mul(base, base)
                power >>= 1
            return R

        M_t = mat_pow(M, t)

        # 3. 计算 v_t = M^t · v_0，其中 v_0 全为 1
        v_t = [sum(row) % MOD for row in M_t]

        # 4. 统计初始字符串中各字符出现次数
        cnt = [0]*26
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1

        # 5. 组合计算最终答案
        ans = 0
        for i in range(26):
            ans = (ans + cnt[i] * v_t[i]) % MOD

        return ans