LeetCode 3337: Total Characters in String After Transformations II

In this article, we’ll walk through a clever solution to the problem “Total Characters in String After Transformations II” using matrix exponentiation. The challenge lies in transforming a string T times, where each character can expand into multiple others and T can be as large as 10⁹. Let's break it down!

---

Problem Summary

You’re given:

• A string s of lowercase English letters.

• An integer t, the number of transformations to perform.

• A list nums of length 26, where nums[i] tells how many next letters each character transforms into.

One Transformation Rule:

If nums[0] = 2, then character 'a' becomes 'b' and 'c'.

After t transformations, the string grows rapidly. Your task is to return the length of the final string modulo (10^9 + 7).

---

Key Insight

Instead of simulating each transformation step-by-step, which is too slow for large t, we treat this as a linear recurrence problem and use matrix exponentiation to compute the result efficiently.

---

Step-by-Step Solution

Step 1: Build the Transformation Matrix

Each character maps to others based on nums. So, we construct a 26x26 matrix M where M[i][j] is the number of times letter i becomes letter j in one transformation.

MOD = 10**9 + 7

class Solution:
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        M = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for k in range(1, nums[i] + 1):
                j = (i + k) % 26
                M[i][j] += 1

For example, if 'a' becomes 'b' and 'c', we set M[0][1] = 1 and M[0][2] = 1.

---

Step 3: Raise the Matrix to Power t

We apply fast matrix exponentiation to simulate t rounds of transformation.

    def matrix_pow(self, mat, power):
        n = len(mat)
        result = [[int(i == j) for j in range(n)] for i in range(n)]
        while power:
            if power % 2:
                result = self.matrix_mult(result, mat)
            mat = self.matrix_mult(mat, mat)
            power //= 2
        return result

This function raises the matrix to the tth power by repeatedly squaring.

---

Step 4: Matrix Multiplication Helper

We need a helper to multiply two matrices under modulo arithmetic.

def matrix_mult(self, A, B):
    n = len(A)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if A[i][k] == 0:
                continue
            for j in range(n):
                result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % MOD
    return result

This handles matrix multiplication efficiently, skipping zeroes for optimization.

---

Step 5: Count Initial Character Frequencies

We count how many times each character appears in the original string.

count = [0] * 26
for ch in s:
    count[ord(ch) - ord('a')] += 1

---

Step 6: Multiply with Powered Matrix to Get Final Length

We multiply the original character frequency vector by the powered matrix to get the final count of all characters after t transformations.

M_t = self.matrix_pow(M, t)
result = 0
for i in range(26):
    for j in range(26):
        result = (result + count[i] * M_t[i][j]) % MOD
return result

This sums up the total number of characters and returns the answer modulo 10^9+7.

MOD = 10**9 + 7

class Solution:
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        # Initialize 26x26 transformation matrix
        M = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for k in range(1, nums[i] + 1):
                j = (i + k) % 26
                M[i][j] += 1

        # Raise the transformation matrix to power t
        M_t = self.matrix_pow(M, t)

        # Count the frequency of each letter in the initial string
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1

        # Calculate the total length after t transformations
        result = 0
        for i in range(26):
            for j in range(26):
                result = (result + count[i] * M_t[i][j]) % MOD

        return result

    def matrix_pow(self, mat, power):
        n = len(mat)
        result = [[int(i == j) for j in range(n)] for i in range(n)]
        while power:
            if power % 2:
                result = self.matrix_mult(result, mat)
            mat = self.matrix_mult(mat, mat)
            power //= 2
        return result

    def matrix_mult(self, A, B):
        n = len(A)
        result = [[0] * n for _ in range(n)]
        for i in range(n):
            for k in range(n):
                if A[i][k] == 0:
                    continue
                for j in range(n):
                    result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % MOD
        return result