Welcome to Subscribe On Youtube

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

  • 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; } } 
  • 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; } }; 
  • 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 
  • 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 } 
  • 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); }

All Problems

All Solutions