Skip to content

3337. Total Characters in String After Transformations II

Description

You are given a string s consisting of lowercase English letters, an integer t representing the number of transformations to perform, and an array nums of size 26. In one transformation, every character in s is replaced according to the following rules:

  • Replace s[i] with the next nums[s[i] - 'a'] consecutive characters in the alphabet. For example, if s[i] = 'a' and nums[0] = 3, the character 'a' transforms into the next 3 consecutive characters ahead of it, which results in "bcd".
  • The transformation wraps around the alphabet if it exceeds 'z'. For example, if s[i] = 'y' and nums[24] = 3, the character 'y' transforms into the next 3 consecutive characters ahead of it, which results in "zab".

Return the length of the resulting string after exactly t transformations.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: 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]

Output: 7

Explanation:

  • First Transformation (t = 1):

    • 'a' becomes 'b' as nums[0] == 1
    • 'b' becomes 'c' as nums[1] == 1
    • 'c' becomes 'd' as nums[2] == 1
    • 'y' becomes 'z' as nums[24] == 1
    • 'y' becomes 'z' as nums[24] == 1
    • String after the first transformation: "bcdzz"

  • Second Transformation (t = 2):

    • 'b' becomes 'c' as nums[1] == 1
    • 'c' becomes 'd' as nums[2] == 1
    • 'd' becomes 'e' as nums[3] == 1
    • 'z' becomes 'ab' as nums[25] == 2
    • 'z' becomes 'ab' as nums[25] == 2
    • String after the second transformation: "cdeabab"

  • Final Length of the string: The string is "cdeabab", which has 7 characters.

Example 2:

Input: 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]

Output: 8

Explanation:

  • First Transformation (t = 1):

    • 'a' becomes 'bc' as nums[0] == 2
    • 'z' becomes 'ab' as nums[25] == 2
    • 'b' becomes 'cd' as nums[1] == 2
    • 'k' becomes 'lm' as nums[10] == 2
    • String after the first transformation: "bcabcdlm"

  • Final Length of the string: The string is "bcabcdlm", which has 8 characters.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of lowercase English letters.
  • 1 <= t <= 109
  • nums.length == 26
  • 1 <= nums[i] <= 25

Solutions

Solution 1: Fast Matrix Exponentiation to Accelerate Recurrence We define \(f[i][j]\) as the number of times the \(j\)-th letter appears in the alphabet after \(i\) transformations. Initially, \(f[0][j]\) corresponds to the frequency of the \(j\)-th letter in the input string \(s\).

Since the frequency of each letter after a transformation affects the next transformation, and the total number of transformations \(t\) can be large, we can accelerate this recurrence process using fast matrix exponentiation.

Note that the result can be very large, so we take modulo \(10^9 + 7\).

The time complexity of this approach is \(O(n + \log t \times |\Sigma|^3)\), where \(n\) is the length of the string and \(|\Sigma|\) is the size of the alphabet (in this case, 26). The space complexity is \(O(|\Sigma|^2)\), which is the size of the matrix used for matrix multiplication.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        mod = 10**9 + 7
        m = 26

        cnt = [0] * m
        for c in s:
            cnt[ord(c) - ord("a")] += 1

        matrix = [[0] * m for _ in range(m)]
        for i, x in enumerate(nums):
            for j in range(1, x + 1):
                matrix[i][(i + j) % m] = 1

        def matmul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
            n, p, q = len(a), len(b), len(b[0])
            res = [[0] * q for _ in range(n)]
            for i in range(n):
                for k in range(p):
                    if a[i][k]:
                        for j in range(q):
                            res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod
            return res

        def matpow(mat: List[List[int]], power: int) -> List[List[int]]:
            res = [[int(i == j) for j in range(m)] for i in range(m)]
            while power:
                if power % 2:
                    res = matmul(res, mat)
                mat = matmul(mat, mat)
                power //= 2
            return res

        cnt = [cnt]
        factor = matpow(matrix, t)
        result = matmul(cnt, factor)[0]

        ans = sum(result) % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    private final int mod = (int) 1e9 + 7;

    public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
        final int m = 26;

        int[] cnt = new int[m];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }

        int[][] matrix = new int[m][m];
        for (int i = 0; i < m; i++) {
            int num = nums.get(i);
            for (int j = 1; j <= num; j++) {
                matrix[i][(i + j) % m] = 1;
            }
        }

        int[][] factor = matpow(matrix, t, m);
        int[] result = vectorMatrixMultiply(cnt, factor);
        int ans = 0;
        for (int val : result) {
            ans = (ans + val) % mod;
        }
        return ans;
    }

    private int[][] matmul(int[][] a, int[][] b) {
        int n = a.length;
        int p = b.length;
        int q = b[0].length;
        int[][] res = new int[n][q];
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < p; k++) {
                if (a[i][k] == 0) continue;
                for (int j = 0; j < q; j++) {
                    res[i][j] = (int) ((res[i][j] + 1L * a[i][k] * b[k][j]) % mod);
                }
            }
        }
        return res;
    }

    private int[][] matpow(int[][] mat, int power, int m) {
        int[][] res = new int[m][m];
        for (int i = 0; i < m; i++) {
            res[i][i] = 1;
        }
        while (power > 0) {
            if ((power & 1) != 0) {
                res = matmul(res, mat);
            }
            mat = matmul(mat, mat);
            power >>= 1;
        }
        return res;
    }

    private int[] vectorMatrixMultiply(int[] vector, int[][] matrix) {
        int n = matrix.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = 0; j < n; j++) {
                sum = (sum + 1L * vector[j] * matrix[j][i]) % mod;
            }
            result[i] = (int) sum;
        }
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    static constexpr int MOD = 1e9 + 7;
    static constexpr int M = 26;

    using Matrix = vector<vector<int>>;

    Matrix matmul(const Matrix& a, const Matrix& b) {
        int n = a.size(), p = b.size(), q = b[0].size();
        Matrix res(n, vector<int>(q, 0));
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < p; ++k) {
                if (a[i][k]) {
                    for (int j = 0; j < q; ++j) {
                        res[i][j] = (res[i][j] + 1LL * a[i][k] * b[k][j] % MOD) % MOD;
                    }
                }
            }
        }
        return res;
    }

    Matrix matpow(Matrix mat, int power) {
        Matrix res(M, vector<int>(M, 0));
        for (int i = 0; i < M; ++i) res[i][i] = 1;
        while (power) {
            if (power % 2) res = matmul(res, mat);
            mat = matmul(mat, mat);
            power /= 2;
        }
        return res;
    }

    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        vector<int> cnt(M, 0);
        for (char c : s) {
            cnt[c - 'a']++;
        }

        Matrix matrix(M, vector<int>(M, 0));
        for (int i = 0; i < M; ++i) {
            for (int j = 1; j <= nums[i]; ++j) {
                matrix[i][(i + j) % M] = 1;
            }
        }

        Matrix cntMat(1, vector<int>(M));
        for (int i = 0; i < M; ++i) cntMat[0][i] = cnt[i];

        Matrix factor = matpow(matrix, t);
        Matrix result = matmul(cntMat, factor);

        int ans = 0;
        for (int x : result[0]) {
            ans = (ans + x) % MOD;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
func lengthAfterTransformations(s string, t int, nums []int) int {
    const MOD = 1e9 + 7
    const M = 26

    cnt := make([]int, M)
    for _, c := range s {
        cnt[int(c-'a')]++
    }

    matrix := make([][]int, M)
    for i := 0; i < M; i++ {
        matrix[i] = make([]int, M)
        for j := 1; j <= nums[i]; j++ {
            matrix[i][(i+j)%M] = 1
        }
    }

    matmul := func(a, b [][]int) [][]int {
        n, p, q := len(a), len(b), len(b[0])
        res := make([][]int, n)
        for i := 0; i < n; i++ {
            res[i] = make([]int, q)
            for k := 0; k < p; k++ {
                if a[i][k] != 0 {
                    for j := 0; j < q; j++ {
                        res[i][j] = (res[i][j] + a[i][k]*b[k][j]%MOD) % MOD
                    }
                }
            }
        }
        return res
    }

    matpow := func(mat [][]int, power int) [][]int {
        res := make([][]int, M)
        for i := 0; i < M; i++ {
            res[i] = make([]int, M)
            res[i][i] = 1
        }
        for power > 0 {
            if power%2 == 1 {
                res = matmul(res, mat)
            }
            mat = matmul(mat, mat)
            power /= 2
        }
        return res
    }

    cntMat := [][]int{make([]int, M)}
    copy(cntMat[0], cnt)

    factor := matpow(matrix, t)
    result := matmul(cntMat, factor)

    ans := 0
    for _, v := range result[0] {
        ans = (ans + v) % MOD
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
function lengthAfterTransformations(s: string, t: number, nums: number[]): number {
    const MOD = BigInt(1e9 + 7);
    const M = 26;

    const cnt: number[] = Array(M).fill(0);
    for (const c of s) {
        cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    const matrix: number[][] = Array.from({ length: M }, () => Array(M).fill(0));
    for (let i = 0; i < M; i++) {
        for (let j = 1; j <= nums[i]; j++) {
            matrix[i][(i + j) % M] = 1;
        }
    }

    const matmul = (a: number[][], b: number[][]): number[][] => {
        const n = a.length,
            p = b.length,
            q = b[0].length;
        const res: number[][] = Array.from({ length: n }, () => Array(q).fill(0));
        for (let i = 0; i < n; i++) {
            for (let k = 0; k < p; k++) {
                const aik = BigInt(a[i][k]);
                if (aik !== BigInt(0)) {
                    for (let j = 0; j < q; j++) {
                        const product = aik * BigInt(b[k][j]);
                        const sum = BigInt(res[i][j]) + product;
                        res[i][j] = Number(sum % MOD);
                    }
                }
            }
        }
        return res;
    };

    const matpow = (mat: number[][], power: number): number[][] => {
        let res: number[][] = Array.from({ length: M }, (_, i) =>
            Array.from({ length: M }, (_, j) => (i === j ? 1 : 0)),
        );
        while (power > 0) {
            if (power % 2 === 1) res = matmul(res, mat);
            mat = matmul(mat, mat);
            power = Math.floor(power / 2);
        }
        return res;
    };

    const cntMat: number[][] = [cnt.slice()];
    const factor = matpow(matrix, t);
    const result = matmul(cntMat, factor);

    let ans = 0n;
    for (const v of result[0]) {
        ans = (ans + BigInt(v)) % MOD;
    }
    return Number(ans);
}

Comments