Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

All occurrences of the same letter transform identically, and only the final length is needed. Track letter counts instead of constructing an exponentially growing string. A letter before z advances once, while every z produces both an a and a b.

Approach

Count the initial occurrences of the 26 letters. For each of the t rounds, create a fresh count array. Move each count from a through y to the following letter. Put the old z count into a, and add it to the new b count, which also receives the old a count.

Replace the old array only after the whole round is computed so newly produced letters are not transformed again in that same round. Use modular arithmetic for accumulating counts. After all rounds, return the sum of the 26 counts modulo 1,000,000,007.

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        MOD = 10**9 + 7
        res = 0
        map = [0] * 26

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

        for _ in range(t):
            tmp = [0] * 26
            for i in range(25):
                tmp[i + 1] = map[i]
            tmp[0] = map[25]
            tmp[1] = (tmp[1] + map[25]) % MOD
            map = tmp

        return sum(map) % MOD

Complexity analysis

Let n = s.length. Time: O(n + 26 * t). Auxiliary space: O(26).