題目資訊

題目編號: 3337
題目連結: Total Characters in String After Transformations II
主題: Hash Table, Math, String, Dynamic Programming, Counting

題目敘述

你有一個由小寫英文字母組成的字串 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^9 + 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 \leq s.length \leq 10^5$
s 僅由小寫英文字母組成。
$1 \leq t \leq 10^9$
nums.length == 26
$1 \leq nums[i] \leq 25$

直覺

此問題要求將字串 s 中的每個字符通過一系列轉換進行改變，這些轉換是由整數數組 nums 和一個整數 t 定義的，其中 t 指定要應用多少次轉換。每次轉換根據 nums 數組將一個字符轉換為字母表中後續字符的序列。挑戰在於處理由於重複轉換可能帶來的指數增長的字符串，特別是在 t 允許達到 $10^9$ 的情況下。

解決此問題的關鍵在於認識到直接模擬 t 次轉換在時間和空間上都是不可行的。相反，通過矩陣快速冪方法可以有效地計算多次轉換的結果。

解法

該解法利用線性代數的概念，尤其是矩陣乘法和矩陣快速冪，以有效地計算 t 次轉換的結果。

初始狀態表示：
- 開始時，將字串 s 表示為一個頻率向量 initialCount，這是一個26維的向量（由於有26個小寫英文字母）。向量中索引 i 的每個元素表示字母 i + 'a' 在 s 中的數量。
轉換矩陣構建：
- 構建一個26x26的轉換矩陣 M，每行代表根據 nums 轉換特定字符的結果。具體而言，如果字符 i 根據 nums[i] 轉換，則對於每個從1到 nums[i] 的 j，矩陣條目 M[(i + j) % 26][i] 設置為1，這樣可以在字母表中環繞處理。
矩陣快速冪：
- 計算矩陣 M 的 t 次方，記作 M^t。這個操作通過平方乘法的快速冪方法，高效計算多次轉換的結果。
最後轉換應用：
- 將矩陣 M^t 與初始頻率向量 initialCount 相乘，得到一個新的向量 finalCount。finalCount 中的每個條目表示 t 次轉換後每個字符的數量。
計算最終長度：
- 將 finalCount 的所有元素加總，以確定轉換後字符串的總長度。由於長度可能很大，將結果對 $10^9 + 7$ 取模，以確保結果在約束范圍內。

此矩陣快速冪方法有效地計算多次轉換的結果，而不需要顯式地擴展字符串，這在可能出現字符串長度指數增長的情況下尤為重要。

程式碼

C++

#include <array>
#include <vector>
#include <string>
using namespace std;

class Solution {
    static constexpr long long MOD = 1'000'000'007;
    using Mat = array<array<long long, 26>, 26>; // 26x26 矩陣類型的別名
    using Vec = array<long long, 26>;            // 26 元素向量類型的別名

    /* -------- 矩陣運算 -------- */

    // 矩陣相乘：將兩個 26x26 矩陣 A 和 B 相乘
    static Mat mulMat(const Mat& A, const Mat& B) {
        Mat C{}; // 將結果矩陣初始化為零
        for (int i = 0; i < 26; ++i)
            for (int k = 0; k < 26; ++k)
                if (A[i][k]) {
                    long long aik = A[i][k];
                    for (int j = 0; j < 26; ++j) {
                        C[i][j] += aik * B[k][j] % MOD;
                        if (C[i][j] >= MOD)
                            C[i][j] -= MOD; // 確保 C[i][j] 在 MOD 範圍內
                    }
                }
        return C;
    }

    // 矩陣-向量相乘：將矩陣 A 與向量 v 相乘
    static Vec mulMatVec(const Mat& A, const Vec& v) {
        Vec res{}; // 將結果向量初始化為零
        for (int i = 0; i < 26; ++i) {
            long long sum = 0;
            for (int j = 0; j < 26; ++j) {
                sum += A[i][j] * v[j] % MOD;
                if (sum >= MOD)
                    sum -= MOD; // 確保 sum 在 MOD 範圍內
            }
            res[i] = sum;
        }
        return res;
    }

    // 矩陣冪次運算：使用平方矩陣冪次的方式計算 base^exp
    static Mat matPow(Mat base, int exp) {
        Mat ret{}; // 單位矩陣初始化
        for (int i = 0; i < 26; ++i)
            ret[i][i] = 1;

        while (exp) {
            if (exp & 1)
                ret = mulMat(ret, base);
            base = mulMat(base, base);
            exp >>= 1;
        }
        return ret;
    }

public:
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        // 1. 將初始字串轉換為 26 維的頻率向量
        Vec initialCount{};
        for (char c : s)
            initialCount[c - 'a']++;

        // 2. 為一次轉換建立 26x26 的轉換矩陣 M
        Mat M{}; // 初始化為零
        for (int i = 0; i < 26; ++i)
            for (int j = 1; j <= nums[i]; j++)
                M[(i + j) % 26][i] = 1;

        // 3. 計算 M^t (M 的 t 次冪)
        Mat Mt = matPow(M, t);

        // 4. 將結果轉換矩陣與初始向量相乘，並將元素相加以獲取最終長度
        Vec finalCount = mulMatVec(Mt, initialCount);
        long long result = 0;
        for (long long x : finalCount) {
            result += x;
            if (result >= MOD)
                result -= MOD; // 確保 result 在 MOD 範圍內
        }
        return static_cast<int>(result);
    }
};

Python

from typing import List

class Solution:
    MOD = 1_000_000_007

    @staticmethod
    def mulMat(A, B):
        C = [[0] * 26 for _ in range(26)]  # 結果矩陣初始化為零
        for i in range(26):
            for k in range(26):
                if A[i][k]:
                    aik = A[i][k]
                    for j in range(26):
                        C[i][j] += aik * B[k][j] % Solution.MOD
                        if C[i][j] >= Solution.MOD:
                            C[i][j] -= Solution.MOD  # 確保 C[i][j] 在 MOD 內
        return C

    @staticmethod
    def mulMatVec(A, v):
        res = [0] * 26  # 結果向量初始化為零
        for i in range(26):
            sum = 0
            for j in range(26):
                sum += A[i][j] * v[j] % Solution.MOD
                if sum >= Solution.MOD:
                    sum -= Solution.MOD  # 確保 sum 在 MOD 內
            res[i] = sum
        return res

    @staticmethod
    def matPow(base, exp):
        ret = [[0] * 26 for _ in range(26)]  # 單位矩陣初始化
        for i in range(26):
            ret[i][i] = 1

        while exp:
            if exp & 1:
                ret = Solution.mulMat(ret, base)
            base = Solution.mulMat(base, base)
            exp >>= 1
        return ret

    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        # 1. 將初始字串轉換為一個26維頻率向量
        initialCount = [0] * 26
        for c in s:
            initialCount[ord(c) - ord('a')] += 1

        # 2. 為一個轉換建立26x26轉換矩陣M
        M = [[0] * 26 for _ in range(26)]  # 初始化為零
        for i in range(26):
            for j in range(1, nums[i] + 1):
                M[(i + j) % 26][i] = 1

        # 3. 計算 M^t (M 的 t 次方)
        Mt = self.matPow(M, t)

        # 4. 將結果轉換矩陣與初始向量相乘
        #    並將元素相加得到最終長度
        finalCount = self.mulMatVec(Mt, initialCount)
        result = 0
        for x in finalCount:
            result += x
            if result >= self.MOD:
                result -= self.MOD  # 確保結果在 MOD 內
        return result

複雜度分析

時間複雜度: $O(26^3 \log t + n)$
時間複雜度可以細分為以下幾個部分：
1. 矩陣乘法與矩陣冪運算： 矩陣乘法（包括矩陣-矩陣和矩陣-向量的乘積）涉及 26x26 的矩陣，因此每次乘法運算需要 $O(26^3)$ 次操作。利用快速冪進行矩陣冪運算需要 $\log t$ 次乘法，導致 $O(26^3 \log t)$ 的時間複雜度。
2. 初始向量設定與最終計算： 建立初始頻率向量需要遍歷字串 s，這需要 $O(n)$。最終長度是通過對結果向量的元素求和得到的，這實際上是另一個 $O(26)$ 的操作，與矩陣運算相比可以忽略不計。
因此，整體時間複雜度主要由矩陣運算支配，即 $O(26^3 \log t + n)$。
空間複雜度: $O(26^2)$
空間複雜度是由儲存 26x26 的轉換矩陣和計算中使用的附加向量決定的：
1. 矩陣儲存： 主要空間由 26x26 的矩陣消耗，即 $O(26^2)$。
2. 向量儲存： 頻率向量的大小為 26，即 $O(26)$，但相較於矩陣儲存要小得多。
由於矩陣的空間需求占主導地位，因此空間複雜度是 $O(26^2)$。

CS Note
En

Leetcode 3337. Total Characters in String After Transformations II

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析