Problem of The Day: Total Characters in String After Transformations I

Problem Statement

leetcode problem link

Brute Force [TLE]

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        hash_map = defaultdict()
        st = ''.join(list(s))
        MOD = 10 ** 9 + 7
        for _ in range(t):
            for c in st:
                if c == 'z':
                    hash_map[c] = 'ab'
                else:
                    next_char = chr((ord(c) - ord('a') + 1) % 26 + ord('a'))
                    hash_map[c] = next_char
            temp = []
            for c in st:
                temp.append(hash_map[c])
            st = ''.join(temp)
        return len(st)

Editorial

Approach: Recurrence

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        mod = 10**9 + 7
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - ord("a")] += 1
        for round in range(t):
            nxt = [0] * 26
            nxt[0] = cnt[25]
            nxt[1] = (cnt[25] + cnt[0]) % mod
            for i in range(2, 26):
                nxt[i] = cnt[i - 1]
            cnt = nxt
        ans = sum(cnt) % mod
        return ans