Problem Description

You have a string s and need to perform t transformations on it. In each transformation, every character in the string follows these replacement rules:

• If the character is 'z', it becomes the string "ab"
• For any other character, it becomes the next letter in the alphabet (e.g., 'a' → 'b', 'b' → 'c', etc.)

After applying exactly t transformations, return the length of the resulting string modulo 10^9 + 7.

For example, if we start with "a" and apply 1 transformation:

• 'a' becomes 'b'
• The length is 1

If we start with "z" and apply 1 transformation:

• 'z' becomes "ab"
• The length is 2

The solution uses dynamic programming to track the count of each letter after each transformation. The array f[i][j] represents how many times the j-th letter of the alphabet appears after i transformations.

The key insight is that after each transformation:

• Letter 'a' (index 0) comes from previous 'z' characters
• Letter 'b' (index 1) comes from both previous 'a' and 'z' characters (since 'z' → "ab")
• All other letters (indices 2-25) come from the previous letter in the alphabet

The final answer is the sum of all letter counts after t transformations.

Intuition

The key observation is that we don't need to actually build the transformed string - we only need to count its length. Since each character transforms independently, we can track how many of each letter exist after each transformation.

Think about what happens to each letter:

• 'a' → 'b'
• 'b' → 'c'
• ...
• 'y' → 'z'
• 'z' → "ab" (special case that creates two characters)

This means after one transformation:

• All 'a's become 'b's
• All 'b's become 'c's
• ...
• All 'z's split into 'a's and 'b's

Since letters shift in a predictable pattern, we can track the count of each letter through transformations. If we know we have 5 'a's before a transformation, we know we'll have 5 'b's after it. If we have 3 'z's, we'll get 3 new 'a's and 3 new 'b's.

This naturally leads to a dynamic programming approach where we maintain a frequency array for each transformation step. The state f[i][j] represents "after i transformations, how many times does the j-th letter appear?"

The recurrence relations become clear:

• f[i][0] (count of 'a') = f[i-1][25] (previous 'z's become 'a's)
• f[i][1] (count of 'b') = f[i-1][0] + f[i-1][25] (previous 'a's shift to 'b', plus 'z's also create 'b's)
• For j >= 2: f[i][j] = f[i-1][j-1] (each letter shifts from the previous one)

The total length after t transformations is simply the sum of all letter counts at that step.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

We implement the solution using a 2D dynamic programming table f where f[i][j] represents the count of the j-th letter (0-indexed, where 0 is 'a', 1 is 'b', ..., 25 is 'z') after i transformations.

Initialization:

f = [[0] * 26 for _ in range(t + 1)]
for c in s:
    f[0][ord(c) - ord("a")] += 1

We create a (t+1) × 26 matrix initialized with zeros. The first row f[0] stores the initial frequency of each letter in the string s.

State Transition: For each transformation i from 1 to t, we update the frequency of each letter based on the transformation rules:

for i in range(1, t + 1):
    f[i][0] = f[i - 1][25]              # 'z' → 'a' (first part of "ab")
    f[i][1] = f[i - 1][0] + f[i - 1][25] # 'a' → 'b' and 'z' → 'b' (second part of "ab")
    for j in range(2, 26):
        f[i][j] = f[i - 1][j - 1]       # each letter shifts to the next

The recurrence relations are:

• f[i][0] = f[i-1][25]: Only 'z' from the previous step produces 'a'
• f[i][1] = f[i-1][0] + f[i-1][25]: Both 'a' (shifts to 'b') and 'z' (produces 'b' as part of "ab") contribute to 'b'
• f[i][j] = f[i-1][j-1] for j ≥ 2: Each letter simply shifts to the next letter in the alphabet

Final Calculation:

mod = 10**9 + 7
return sum(f[t]) % mod

The total length after t transformations is the sum of all letter frequencies in row f[t]. We apply modulo 10^9 + 7 to handle large numbers.

Time Complexity: O(26 × t) = O(t) since we iterate through 26 letters for each of t transformations.

Space Complexity: O(26 × t) = O(t) for storing the 2D DP table.

Example Walkthrough

Let's walk through a small example with string s = "az" and t = 2 transformations.

Initial Setup:

• Start with string "az"
• Initialize DP table f[3][26] (for t=0, t=1, t=2)
• Set initial frequencies: f[0][0] = 1 (one 'a'), f[0][25] = 1 (one 'z')

After 1st Transformation (t=1):

Original characters transform:

• 'a' → 'b'
• 'z' → "ab"

Using our recurrence relations:

• f[1][0] = f[0][25] = 1 (the 'z' creates an 'a')
• f[1][1] = f[0][0] + f[0][25] = 1 + 1 = 2 (the original 'a' becomes 'b', and 'z' also creates a 'b')
• f[1][j] = f[0][j-1] for j ≥ 2 (all zero since we had no letters 'b' through 'y')

String after 1st transformation: "bab" (length = 3) Letter counts: 1 'a', 2 'b's, 0 for all others

After 2nd Transformation (t=2):

The string "bab" transforms:

• 'b' → 'c' (happens twice)
• 'a' → 'b'

Using our recurrence relations:

• f[2][0] = f[1][25] = 0 (no 'z' from previous step)
• f[2][1] = f[1][0] + f[1][25] = 1 + 0 = 1 (the 'a' from step 1 becomes 'b')
• f[2][2] = f[1][1] = 2 (the 2 'b's from step 1 become 2 'c's)
• f[2][j] = f[1][j-1] for j ≥ 3 (all zero)

String after 2nd transformation: "ccb" (length = 3) Letter counts: 0 'a's, 1 'b', 2 'c's, 0 for all others

Final Answer: Sum of all frequencies after 2 transformations: 0 + 1 + 2 + 0 + ... + 0 = 3 Return: 3 % (10^9 + 7) = 3

This example demonstrates how the DP table tracks letter frequencies through transformations, with special handling for 'z' → "ab" that increases the total length.

Solution Implementation

Time and Space Complexity

The time complexity of this algorithm is O(t × 26), which can be written as O(t × |Σ|) where |Σ| = 26 represents the size of the alphabet (26 lowercase English letters).

The algorithm consists of:

1. Initial setup: O(n) where n is the length of string s, to populate the first row of the frequency matrix
2. Main computation: Two nested loops - the outer loop runs t times and the inner loop runs 26 times, giving us O(t × 26)
3. Final summation: O(26) to sum up the last row

The dominant term is O(t × 26), so the overall time complexity is O(t × |Σ|).

The space complexity is O((t + 1) × 26), which simplifies to O(t × |Σ|). The algorithm creates a 2D matrix f with dimensions (t + 1) × 26 to store the frequency counts for each character at each transformation step. Since we're storing all intermediate results from transformation 0 to transformation t, the space requirement is proportional to both t and the alphabet size |Σ|.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Apply Modulo During Intermediate Calculations

The most common pitfall is only applying modulo at the final step when calculating the sum. Since the counts can grow exponentially with each transformation, integer overflow can occur even before reaching the final summation.

Problematic Code:

# Only applying modulo at the end
for transformation in range(1, t + 1):
    dp[transformation][0] = dp[transformation - 1][25]
    dp[transformation][1] = dp[transformation - 1][0] + dp[transformation - 1][25]
    for char_idx in range(2, ALPHABET_SIZE):
        dp[transformation][char_idx] = dp[transformation - 1][char_idx - 1]

# Overflow may have already occurred before this point
total_length = sum(dp[t]) % MOD

Solution: Apply modulo operation during each update to prevent overflow:

for transformation in range(1, t + 1):
    dp[transformation][0] = dp[transformation - 1][25] % MOD
    dp[transformation][1] = (dp[transformation - 1][0] + dp[transformation - 1][25]) % MOD
    for char_idx in range(2, ALPHABET_SIZE):
        dp[transformation][char_idx] = dp[transformation - 1][char_idx - 1] % MOD

2. Incorrect Understanding of the 'z' → "ab" Transformation

A critical misunderstanding is thinking that 'z' only transforms to 'a' OR 'b', rather than contributing to both characters simultaneously. This leads to incorrect state transitions.

Incorrect Implementation:

# Wrong: treating 'z' as transforming to either 'a' or 'b', not both
dp[transformation][0] = dp[transformation - 1][25]
dp[transformation][1] = dp[transformation - 1][0]  # Missing the contribution from 'z'

Correct Implementation:

# Correct: 'z' contributes to both 'a' and 'b'
dp[transformation][0] = dp[transformation - 1][25]
dp[transformation][1] = dp[transformation - 1][0] + dp[transformation - 1][25]

3. Space Optimization Pitfall When Using Rolling Array

When optimizing space by using only two arrays (current and previous), a common mistake is updating values in-place without proper ordering, causing data corruption.

Problematic Space-Optimized Code:

prev = [0] * 26
curr = [0] * 26
# Initialize prev with character counts from s

for _ in range(t):
    curr[0] = prev[25]
    curr[1] = prev[0] + prev[25]
    for j in range(2, 26):
        curr[j] = prev[j - 1]
    prev = curr  # Wrong: this creates a reference, not a copy!

Solution: Use proper array copying or swapping:

for _ in range(t):
    curr[0] = prev[25] % MOD
    curr[1] = (prev[0] + prev[25]) % MOD
    for j in range(2, 26):
        curr[j] = prev[j - 1] % MOD
    prev, curr = curr, prev  # Proper swapping

Or use array copying:

    prev = curr[:]  # Create a copy, not a reference