Difficulty: 🟡 Medium
Topics: Hash Table, Math, String, Dynamic Programming, Counting

Solution

Problem Understanding

The problem gives us a string s and an integer t. We repeatedly apply a transformation exactly t times.

During one transformation:

Every character from 'a' to 'y' becomes the next character in the alphabet.
The character 'z' becomes the string "ab".

After all transformations are complete, we must return the length of the final string modulo 10^9 + 7.

The important detail is that we are only asked for the final length, not the actual transformed string. This distinction completely changes the nature of the problem. Constructing the real string quickly becomes infeasible because the string can grow exponentially when many 'z' characters appear.

For example:

'a' → 'b' → 'c' → ...
'y' → 'z' → "ab"
After a 'z' expansion, both 'a' and 'b' continue transforming independently.

The constraints are large:

s.length <= 10^5
t <= 10^5

These limits immediately tell us that simulating the actual string character by character is too expensive. Even if each transformation were linear, the string itself can become enormous.

The key observation is that we only care about character counts and total length, not the exact ordering of characters.

Several edge cases are important:

Strings containing many 'z' characters, because those increase the length.
Large values of t, where repeated expansions occur.
Small strings like "z" or "a" that help verify the transformation logic.
Cases where no expansion happens yet, such as transforming "a" only a few times before it reaches 'z'. The problem asks us to simulate repeated string transformations, but only to determine the final length of the string after t transformations, not the actual final string itself. We are given an initial string s, and each character evolves independently according to fixed rules applied simultaneously in each transformation step.

Each character transforms as follows: if the character is 'z', it becomes the two-character string "ab", effectively increasing length by one. For any other lowercase letter, it simply becomes the next letter in the alphabet, which preserves length.

The key observation is that we never need to track the full string content, only how many characters each character contributes after t steps.

The input size constraints are large, with s.length and t both up to 10^5. This makes any simulation of the full string impossible because the string can grow exponentially due to repeated "z" -> "ab" expansions.

Important edge cases include strings consisting entirely of 'z', which cause exponential growth, strings with no 'z' which only shift letters, and large t values where recursive expansion chains matter deeply. We are guaranteed lowercase English letters only, which simplifies transitions.

Approaches

Brute Force Approach

A direct simulation would repeatedly build the transformed string.

For every transformation:

Traverse the current string.
Replace 'z' with "ab".
Replace every other character with the next character.
Construct the new string.

This approach is correct because it exactly follows the rules given in the problem statement.

However, the string length can grow extremely quickly. Every 'z' increases the length by one additional character. After many transformations, the string may become astronomically large.

In the worst case, the runtime and memory usage become proportional to the final string size, which is far beyond the constraints.

Optimal Approach

The crucial insight is that the transformation only depends on character frequencies.

Instead of storing the entire string, we store:

How many 'a' characters exist
How many 'b' characters exist
...
How many 'z' characters exist

We maintain a frequency array of size 26.

During each transformation:

Characters 'a' through 'y' simply shift to the next letter.
Characters 'z' create one 'a' and one 'b'.

This lets us process each transformation in constant time relative to the alphabet size, not the string size.

Since the alphabet contains only 26 lowercase letters, each transformation costs O(26) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Potentially exponential	Potentially exponential	Explicitly constructs the growing string
Optimal	O(26 × t + n)	O(26)	Tracks only character frequencies

Where n is the length of the input string.

Algorithm Walkthrough

Create a frequency array of size 26.

Each index represents a lowercase letter:

index 0 represents 'a'
index 1 represents 'b'
...
index 25 represents 'z'

We count how many times each character appears in the initial string. 2. Repeat the transformation process t times.

For each transformation, create a new frequency array called next_counts. 3. Process characters 'a' through 'y'.

If a character currently has frequency freq[i], then after one transformation it becomes the next character.

So:

'a' contributes to 'b'
'b' contributes to 'c'
...
'y' contributes to 'z'

This is implemented by shifting counts one position to the right. 4. Process character 'z'.

Every 'z' transforms into "ab".

If there are freq[25] copies of 'z', then:

add that amount to 'a'
add that amount to 'b'

Apply modulo operations.

Since the answer can become very large, every update is performed modulo 10^9 + 7. 6. Replace the current frequency array.

After finishing one transformation, assign:

freq = next_counts

Compute the final answer.

After all t transformations, sum all frequencies to get the final string length.

Why it works

The algorithm works because transformations are independent for each character. The future behavior of a character depends only on its current letter, not on neighboring characters or string position.

By storing only frequencies, we preserve all information needed to determine future transformations. Every transformation updates counts exactly according to the rules, so after t iterations the frequency array represents the same multiset of characters that the actual transformed string would contain.

Therefore, summing the frequencies gives the exact final length. The brute force approach directly simulates each transformation step. For every character in the string, we construct a new string according to the transformation rules. We repeat this process t times.

This approach is correct because it follows the definition exactly. However, it becomes infeasible because the string can grow exponentially when 'z' characters repeatedly expand into two characters. Even moderate values of t will lead to massive memory and time consumption.

Key Insight for Optimization

Instead of simulating the entire string, we track how many characters each letter contributes after a given number of transformations.

Let dp[c][k] represent the number of characters produced by a single character c after k transformations.

We notice two key transitions:

For 'a' to 'y', the character deterministically becomes the next character, so:

dp[c][k] = dp[c+1][k-1]

For 'z', it becomes "ab", so:

dp['z'][k] = dp['a'][k-1] + dp['b'][k-1]

This forms a reverse dynamic programming relation across letters and time. We compute values bottom-up for increasing k.

Finally, we sum contributions for each character in s.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n · growth)	O(n · growth)	Explicitly builds transformed strings
Optimal DP	O(26 · t + n)	O(26)	Tracks character contribution counts only

Algorithm Walkthrough

We define a DP table where dp[i][j] represents the length contribution of character (i-th letter, 0=a ... 25=z) after j transformations. This avoids building strings and instead models growth numerically.
Initialize the base case for t = 0, where each character contributes exactly 1, because no transformations have been applied.
Iterate over transformation steps from 1 to t. For each step, compute contributions for each character from 'a' to 'z'.
For characters 'a' through 'y', their contribution at step j equals the contribution of the next character at step j-1, since they simply shift forward in the alphabet.
For 'z', the transformation splits into "ab", so its contribution becomes the sum of contributions of 'a' and 'b' at step j-1.
After filling the DP table up to step t, compute the final answer by summing the contributions for each character in the input string s at step t.
Apply modulo 10^9 + 7 at every addition to avoid overflow.

Why it works

The algorithm works because transformations are linear and independent per character. Each character's contribution depends only on its future state, and all transitions are deterministic. This allows us to precompute transformation outcomes using dynamic programming over a fixed alphabet size, ensuring correctness without explicit string simulation.

Python Solution

class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        MOD = 10**9 + 7

        counts = [0] * 26

        for ch in s:
            counts[ord(ch) - ord('a')] += 1

        for _ in range(t):
            next_counts = [0] * 26

            for i in range(25):
                next_counts[i + 1] = (
                    next_counts[i + 1] + counts[i]
                ) % MOD

            z_count = counts[25]

            next_counts[0] = (next_counts[0] + z_count) % MOD
            next_counts[1] = (next_counts[1] + z_count) % MOD

            counts = next_counts

        return sum(counts) % MOD

The implementation begins by counting the frequency of each character in the input string.

The array counts always represents the current number of occurrences of every letter. Instead of building strings repeatedly, the algorithm updates this compact representation.

For each transformation:

Characters from 'a' to 'y' shift forward by one position.
'z' contributes to both 'a' and 'b'.

A fresh array next_counts is used for every step so updates do not interfere with values still needed during the current iteration.

Finally, the sum of all frequencies equals the final string length. from typing import List

class Solution: def lengthAfterTransformations(self, s: str, t: int) -> int: MOD = 10**9 + 7

    # dp[i] = contribution vector for current step
    dp = [1] * 26
    
    for _ in range(t):
        new_dp = [0] * 26
        
        # 'a' to 'y'
        for i in range(25):
            new_dp[i] = dp[i + 1] % MOD
        
        # 'z' -> "ab"
        new_dp[25] = (dp[0] + dp[1]) % MOD
        
        dp = new_dp
    
    # map characters in s using final dp
    result = 0
    for ch in s:
        result = (result + dp[ord(ch) - ord('a')]) % MOD
    
    return result


### Code Explanation

We maintain a single DP array of size 26, where each entry represents how many characters a letter contributes after a given number of transformations. Initially, every letter contributes 1 at time 0.

For each transformation step, we construct a new DP state. Letters `'a'` through `'y'` simply inherit the value of the next letter from the previous state. The `'z'` case is special because it splits into two letters, so we sum contributions from `'a'` and `'b'`.

Finally, we compute the answer by summing the contributions of each character in the input string using the final DP state.

## Go Solution

```go
func lengthAfterTransformations(s string, t int) int {
	const MOD int = 1_000_000_007

	counts := make([]int, 26)

	for _, ch := range s {
		counts[ch-'a']++
	}

	for step := 0; step < t; step++ {
		nextCounts := make([]int, 26)

		for i := 0; i < 25; i++ {
			nextCounts[i+1] = (nextCounts[i+1] + counts[i]) % MOD
		}

		zCount := counts[25]

		nextCounts[0] = (nextCounts[0] + zCount) % MOD
		nextCounts[1] = (nextCounts[1] + zCount) % MOD

		counts = nextCounts
	}

	answer := 0

	for _, value := range counts {
		answer = (answer + value) % MOD
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

Slices are used for the frequency arrays. Since Go integers can overflow on some platforms if values become too large, modulo operations are applied consistently during updates.

Unlike Python, Go does not have arbitrary precision integers by default, so careful modulo handling is important. const MOD = 1000000007

dp := make([]int, 26)
for i := 0; i < 26; i++ {
    dp[i] = 1
}

for step := 0; step < t; step++ {
    newDp := make([]int, 26)

    for i := 0; i < 25; i++ {
        newDp[i] = dp[i+1] % MOD
    }

    newDp[25] = (dp[0] + dp[1]) % MOD

    dp = newDp
}

result := 0
for _, ch := range s {
    idx := int(ch - 'a')
    result = (result + dp[idx]) % MOD
}

return result

}


### Go-Specific Notes

Go uses explicit slices instead of lists, so we allocate arrays using `make([]int, 26)`. Integer overflow is handled manually using modulo operations since Go integers do not automatically wrap. The logic mirrors the Python version exactly, with direct index-based updates.

## Worked Examples

### Example 1

Input:

s = "abcyy" t = 2


Initial frequencies:

| Character | Count |
| --- | --- |
| a | 1 |
| b | 1 |
| c | 1 |
| y | 2 |

### Transformation 1

| Original | Becomes |
| --- | --- |
| a | b |
| b | c |
| c | d |
| y | z |
| y | z |

New string:

"bcdzz"


Updated frequencies:

| Character | Count |
| --- | --- |
| b | 1 |
| c | 1 |
| d | 1 |
| z | 2 |

Length = 5

### Transformation 2

| Original | Becomes |
| --- | --- |
| b | c |
| c | d |
| d | e |
| z | ab |
| z | ab |

New string:

"cdeabab"


Updated frequencies:

| Character | Count |
| --- | --- |
| a | 2 |
| b | 2 |
| c | 1 |
| d | 1 |
| e | 1 |

Final length:

2 + 2 + 1 + 1 + 1 = 7


Answer:


### Example 2

Input:

s = "azbk" t = 1


Initial frequencies:

| Character | Count |
| --- | --- |
| a | 1 |
| b | 1 |
| k | 1 |
| z | 1 |

### Transformation 1

| Original | Becomes |
| --- | --- |
| a | b |
| z | ab |
| b | c |
| k | l |

New string:

"babcl"


Updated frequencies:

| Character | Count |
| --- | --- |
| a | 1 |
| b | 2 |
| c | 1 |
| l | 1 |

Final length:

1 + 2 + 1 + 1 = 5


Answer:


## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n + 26 × t) | Initial counting takes O(n), each transformation processes 26 letters |
| Space | O(26) | Only fixed-size frequency arrays are stored |

Since the alphabet size is constant, `26 × t` simplifies to `O(t)`, but writing it explicitly makes the reasoning clearer.

The memory usage remains constant regardless of how large the transformed string becomes.

## Test Cases

sol = Solution()

assert sol.lengthAfterTransformations("abcyy", 2) == 7

Provided example with multiple z expansions

assert sol.lengthAfterTransformations("azbk", 1) == 5

Provided example with one z transformation

assert sol.lengthAfterTransformations("a", 1) == 1

a -> b, length unchanged

assert sol.lengthAfterTransformations("y", 1) == 1

y -> z, still length 1

assert sol.lengthAfterTransformations("z", 1) == 2

z -> ab, length increases

assert sol.lengthAfterTransformations("z", 2) == 2

z -> ab -> bc, length remains 2

assert sol.lengthAfterTransformations("zz", 1) == 4

each z expands into two characters

assert sol.lengthAfterTransformations("abc", 0) == 3

no transformations applied

assert sol.lengthAfterTransformations("x", 3) == 3

x -> y -> z -> ab

assert sol.lengthAfterTransformations("zzz", 3) == 6

repeated expansions

assert sol.lengthAfterTransformations("abcdefghijklmnopqrstuvwxyz", 1) == 27

only z increases total length

assert sol.lengthAfterTransformations("a" * 100000, 100000) >= 0

stress test for maximum constraints


## Test Summary

| Test | Why |
| --- | --- |
| `"abcyy", 2` | Validates the main example |
| `"azbk", 1` | Checks mixed transformations |
| `"a", 1` | Simple non-expanding character |
| `"y", 1` | Boundary before z |
| `"z", 1` | Single expansion |
| `"z", 2` | Expansion followed by normal shifts |
| `"zz", 1` | Multiple simultaneous expansions |
| `"abc", 0` | Verifies zero transformations |
| `"x", 3` | Confirms delayed expansion |
| `"zzz", 3` | Repeated growth behavior |
| Full alphabet | Ensures only z changes length |
| Large stress case | Verifies performance constraints |

## Edge Cases

One important edge case occurs when the input contains many `'z'` characters. Since every `'z'` becomes `"ab"`, the string length increases immediately. A naive implementation that repeatedly constructs strings can become extremely slow or run out of memory. The frequency-based approach handles this efficiently because it only updates counts.

Another important case is when transformations do not yet cause expansion. For example, transforming `"a"` several times simply shifts letters forward through the alphabet. The implementation correctly models this using index shifts in the frequency array, without any special handling.

A third important edge case involves delayed expansion. Consider `"x"` with `t = 3`:

x -> y -> z -> ab


The length remains 1 for two transformations and increases only at the third. Incorrect implementations may prematurely expand characters or mis-handle the transition into `'z'`. The algorithm avoids this issue because each transformation is processed independently and exactly matches the stated rules.

Another subtle edge case is very large `t`. Since `t` can be `100000`, repeated string construction is impossible. The implementation remains efficient because every transformation processes only 26 entries, independent of the actual string size.
Input: `s = "abcyy", t = 2`

Initial DP at `t=0`: every character contributes 1.

After `t=1`, each character shifts forward; `'y'` becomes `'z'`.

After `t=2`, `'z'` expands into `"ab"`.

We compute contributions per character rather than full string:

| Step | a | b | c | d | ... | y | z |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | 1 | 1 | 1 |  | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |  | 1 | 1 |
| 2 | 1 | 1 | 1 | 1 |  | 1 | 2 (splits) |

Now sum contributions:

- a → 1
- b → 1
- c → 1
- y → 2
- y → 2

Total = 7

### Example 2

Input: `s = "azbk", t = 1`

At `t=1`:

- a → b
- z → ab
- b → c
- k → l

So contributions

LeetCode 3335 - Total Characters in String After Transformations I

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Approach Comparison

Algorithm Walkthrough

Why it works

Key Insight for Optimization

Complexity Comparison

Algorithm Walkthrough

Why it works

Python Solution

Provided example with multiple z expansions

Provided example with one z transformation

a -> b, length unchanged

y -> z, still length 1

z -> ab, length increases

z -> ab -> bc, length remains 2

each z expands into two characters

no transformations applied

x -> y -> z -> ab

repeated expansions

only z increases total length

stress test for maximum constraints