#3337

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Total Characters in String After Transformations II

Calculate the length of a string after repeated transformations using state transition dynamic programming for large t values efficiently.

hash table math string dynamic programming counting

Problem Statement

You are given a string s of lowercase English letters, an integer t representing the number of transformations, and an array nums of size 26. In each transformation, every character c in s is replaced by a sequence of characters determined by nums[c - 'a'], effectively expanding the string according to the mapping.

Return the total number of characters in the string after performing exactly t transformations. Since the result can be very large, return it modulo 10^9 + 7.

Examples

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

First Transformation (t = 1): Second Transformation (t = 2): 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

First Transformation (t = 1): 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

Solution Approach

Model Transformations with a Matrix

Represent each character as a vector and construct a 26x26 matrix where entry (i,j) represents how many times character j appears when character i transforms. This captures all state transitions.

Apply Matrix Exponentiation

Raise the transformation matrix to the t-th power using fast exponentiation. Multiply the initial character count vector by the powered matrix to compute the total counts after t transformations efficiently.

Compute Total Length Modulo

Sum all entries in the resulting vector to obtain the final string length. Apply modulo 10^9 + 7 to prevent integer overflow and comply with problem constraints.

Complexity Analysis

Metric	Value
Time	O(n + \log t \times
Space	O(

Time complexity is O(n + log t * |Σ|^3) due to matrix exponentiation on a 26x26 matrix, and space complexity is O(|Σ|^2) for storing the transformation matrix.

What Interviewers Usually Probe

Recognize the problem as state transition dynamic programming suitable for matrix modeling.
Identify that direct simulation will fail for large t due to exponential growth.
Look for modular arithmetic to handle large numeric results.

Common Pitfalls or Variants

Common pitfalls

Trying to simulate all transformations directly, leading to TLE.
Incorrectly building the transformation matrix, mixing row and column meanings.
Forgetting to apply modulo at each multiplication step, causing overflow.

Follow-up variants

Compute the length of the string after transformations but return the full expanded string instead.
Transformations vary per character type with different nums arrays per step.
Consider transformations on multibyte characters or extended alphabets instead of just lowercase letters.

FAQ

What is the main pattern used in Total Characters in String After Transformations II?

It uses state transition dynamic programming with matrix exponentiation to track cumulative character expansions over t transformations.

Why is direct simulation not feasible for large t?

Because each transformation can exponentially increase string length, direct simulation exceeds time limits quickly.

How do you apply the nums array in transformations?

Each character c expands according to nums[c - 'a'], defining how many times each subsequent character appears.

What is the role of modulo 10^9 + 7 in this problem?

It prevents integer overflow and ensures the final length is returned within allowed numerical limits.

Can this approach handle all lowercase letters efficiently?

Yes, the 26x26 matrix captures all lowercase letter transitions and allows fast computation even for very large t.

terminal

Solution

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$.

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

Continue Practicing

#3335 total characters in string after transformations i #3389 minimum operations to make character frequencies equal #3443 maximum manhattan distance after k changes