Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

One transformation is a linear operation on the 26 letter counts: each occurrence of a letter contributes fixed counts to its replacement letters. Repeating that operation t times is matrix exponentiation, allowing a huge number of rounds without simulating them individually.

Approach

Build a 26-by-26 transition matrix. Column i describes one occurrence of letter i; set rows (i + 1) mod 26 through (i + nums[i]) mod 26 to one. The stated replacement lengths keep these destinations distinct within a column.

Compute the matrix's t-th power by binary exponentiation. Start with the identity matrix, multiply the accumulated result by the current base for each set exponent bit, and square the base as the exponent is halved. Reduce all matrix calculations modulo 1,000,000,007.

Multiply the resulting matrix by the initial letter-frequency vector. Each output entry is a final letter count; summing them gives the required length modulo the modulus. The row-destination, column-source convention is used consistently in both construction and application.

MOD = 10**9 + 7

def multiply(a, b):
    new_matrix = [[0] * 26 for _ in range(26)]

    for i in range(26):
        for j in range(26):
            for k in range(26):
                new_matrix[i][j] = (new_matrix[i][j] + a[i][k] * b[k][j]) % MOD

    return new_matrix

def pow_matrix(base, exp):
    new_matrix = [[0] * 26 for _ in range(26)]

    for i in range(26):
        new_matrix[i][i] = 1

    while exp:
        if exp % 2:
            new_matrix = multiply(new_matrix, base)
        base = multiply(base, base)
        exp //= 2

    return new_matrix

class Solution:
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        matrix = [[0] * 26 for _ in range(26)]

        for i in range(26):
            for j in range(1, nums[i] + 1):
                matrix[(i + j) % 26][i] = 1

        final_matrix = pow_matrix(matrix, t)

        map = [0] * 26

        for x in s:
            map[ord(x) - ord('a')] += 1

        res = [0] * 26

        for i in range(26):
            for j in range(26):
                res[i] = (res[i] + final_matrix[i][j] * map[j]) % MOD

        return sum(res) % MOD

Complexity analysis

Let n = s.length and a = sum(nums). Time: O(a + n + 26^3 log t). Auxiliary space: O(26^2).