Skip to main content
Talentd

Total Characters in String After Transformations I - Solution & Explanation

MediumHash TableMathStringDynamic Programming13 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

You are given a string s and an integer t, representing the number of transformations to perform. In one transformation, every character in s is replaced according to the following rules:

  • If the character is 'z', replace it with the string "ab".
  • Otherwise, replace it with the next character in the alphabet. For example, 'a' is replaced with 'b', 'b' is replaced with 'c', and so on.

Return the length of the resulting string after exactly t transformations.

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: s = "abcyy", t = 2

Output: 7

Explanation:

  • First Transformation (t = 1):
    • 'a' becomes 'b'
    • 'b' becomes 'c'
    • 'c' becomes 'd'
    • 'y' becomes 'z'
    • 'y' becomes 'z'
    • String after the first transformation: "bcdzz"
  • Second Transformation (t = 2):
    • 'b' becomes 'c'
    • 'c' becomes 'd'
    • 'd' becomes 'e'
    • 'z' becomes "ab"
    • 'z' becomes "ab"
    • String after the second transformation: "cdeabab"
  • Final Length of the string: The string is "cdeabab", which has 7 characters.

Example 2:

Input: s = "azbk", t = 1

Output: 5

Explanation:

  • First Transformation (t = 1):
    • 'a' becomes 'b'
    • 'z' becomes "ab"
    • 'b' becomes 'c'
    • 'k' becomes 'l'
    • String after the first transformation: "babcl"
  • Final Length of the string: The string is "babcl", which has 5 characters.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of lowercase English letters.
  • 1 <= t <= 105

Approach Overview

Problem Overview: You start with a string s. During each transformation, every character moves to the next letter in the alphabet. When a character reaches 'z', it expands into the two-character string "ab". After performing t transformations, return the total number of characters in the resulting string.

Approach 1: Simulate Transformations with Length Calculation (Time: O(n + 26t), Space: O(26))

Instead of rebuilding the string every round, track how many times each character appears. Use a frequency array of size 26 where count[i] stores the number of occurrences of the i-th letter. For each transformation, shift counts forward: characters 'a' through 'y' move to the next index, while 'z' produces two characters, increasing the counts of 'a' and 'b'. Repeat this update for t rounds. The total length at any step is simply the sum of all frequencies. This approach avoids string concatenation and keeps the state compact using a small fixed array.

The key insight is that the transformation only depends on character counts, not the order of characters. Using counting makes each step constant time with respect to alphabet size. This pattern appears frequently in problems involving repeated string updates and can be viewed as a small-state dynamic programming process combined with simple counting.

Approach 2: Mathematical Simplification Using Exponents (Time: O(n + log t) or O(n + 26t) precompute, Space: O(26))

Each character contributes to the final length depending on how many times it reaches 'z' within t steps. When that happens, the character splits into two new characters which continue transforming independently. Instead of simulating every step, compute how a single character grows after t transformations. Precompute the growth for each letter by observing when the chain hits 'z' and creates additional characters.

This reduces the problem to summing contributions from the initial characters. For example, if a letter becomes 'z' after k steps, the remaining transformations generate extra characters starting from 'a' and 'b'. Using precomputed growth values or exponent-style recurrence avoids repeatedly shifting arrays and scales better when t becomes large. The reasoning relies on simple alphabet arithmetic and ideas commonly used in math-driven DP transitions.

Recommended for interviews: The counting simulation is the expected solution. It shows you recognize that the string order is irrelevant and that only frequencies matter. Brute string simulation would explode in size, while the 26-slot counting DP keeps updates predictable and efficient. The mathematical simplification demonstrates deeper optimization thinking but usually comes after you explain the counting model.

Approach 1: Simulate Transformations with Length Calculation

This approach focuses on simulating each transformation step by step. Begin with the initial length of the string. For each character in the string, calculate the change in length based on the transformation rules. If the character is not 'z', it contributes 1 to the final length; if it is 'z', it contributes 2 due to its transformation to 'ab'. Iterate this process for each transformation up to t times, updating the total length accordingly.

The function total_length_after_transformations simulates each transformation for a given number of t, adjusting the length by accounting for each rule's effect on each character within the string s for t times.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(t * n), where n is the length of the string because it processes every character for each transformation.
Space Complexity: O(n), needing to store the potentially transformed string.

Try this approach in the editor →

Approach 2: Mathematical Simplification Using Exponents

This mathematical method avoids simulating every transformation by leveraging the predictable pattern that the transformations create. Consider that each non-'z' character simply advances through the alphabet. Importantly, 'z' contributes significantly due to its transformation to 'ab'. Devise a formula or recurring relation that describes the total length after t transformations. Solve this by setting up a simulation using mathematical functions that model the string length changes without modifying string values.

The total_length_formula uses the property of exponential growth when 'z' is present, doubling contributions each time transformation occurs. This avoids actually constructing the string, hence limiting memory use and improving performance.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n + log t).
Space Complexity: O(1). This approach eliminates the need to store intermediate string states fully.

Try this approach in the editor →

Approach 3: Recurrence

We define f[i][j] to represent the count of the j-th letter in the alphabet after i transformations. Initially, f[0][j] is the count of the j-th letter in the string s.

After each transformation, the count of the j-th letter in the alphabet can be calculated as follows:

$ \begin{align} f[i][0] &= f[i - 1][25] \ f[i][1] &= f[i - 1][0] + f[i - 1][25] \ f[i][2] &= f[i - 1][1] \ f[i][3] &= f[i - 1][2] \ &\vdots \ f[i][25] &= f[i - 1][24] \end{align}

The answer is f[t][0] + f[t][1] + ldots + f[t][25].

Since the answer can be very large, we take the result modulo 10^9 + 7.

The time complexity is O(t times |\Sigma|), and the space complexity is O(t times |\Sigma|), where |\Sigma|$ is the size of the alphabet.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulate Transformations with Length Calculation

Time Complexity: O(t * n), where n is the length of the string because it processes every character for each transformation.
Space Complexity: O(n), needing to store the potentially transformed string.

Mathematical Simplification Using Exponents

Time Complexity: O(n + log t).
Space Complexity: O(1). This approach eliminates the need to store intermediate string states fully.

Recurrence—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive String SimulationExponentialO(n * growth)Conceptual understanding only; impractical because the string grows rapidly
Simulate with Character CountingO(n + 26t)O(26)Standard solution when t is moderate; avoids constructing the string
Mathematical Contribution / Precomputed GrowthO(n + log t) or O(n + 26t)O(26)Large t values where repeated simulation becomes expensive

Video Solution

Total Characters in String After Transformations I | Made Easy | Leetcode 3335 | codestorywithMIK • codestorywithMIK • 13,477 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Total Characters in String After Transformations I easy or hard?
The problem is rated Medium because the straightforward simulation quickly becomes infeasible as the string grows. The key difficulty is recognizing that character order does not matter and switching to a frequency-based dynamic programming model.
Total Characters in String After Transformations I Python/Java solution
Both Python and Java implementations typically use an integer array of size 26 to track character frequencies. Each iteration shifts counts for 'a' through 'y' and handles the special expansion rule for 'z'. After t iterations, summing the array returns the total number of characters.
How to solve Total Characters in String After Transformations I in O(n)?
Achieving near O(n) work requires avoiding explicit string simulation. Convert the input string into character frequencies, then compute how each letter contributes to the final length after t steps using a recurrence or precomputed growth values. Summing these contributions gives the final character count without constructing intermediate strings.
What is the best approach for Total Characters in String After Transformations I?
The most practical solution tracks how many times each letter appears using a 26-element frequency array. Each transformation shifts counts forward and handles the special rule where 'z' becomes 'ab'. This counting dynamic programming approach runs in O(n + 26t) time and O(26) space and avoids building the exponentially growing string.
Is Total Characters in String After Transformations I asked at Google/Amazon/Meta?
Problems involving repeated transformations, character counting, and state transitions appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may not always appear, the pattern of converting string evolution into frequency-based dynamic programming is common in interview rounds.
What data structure is used in Total Characters in String After Transformations I?
The core data structure is a fixed-size array or hash table storing counts for the 26 lowercase letters. This structure allows constant-time updates for each transformation step and eliminates the need to manipulate large strings.
What is the time complexity of Total Characters in String After Transformations I?
The typical optimized solution runs in O(n + 26t) time. Building the initial frequency array takes O(n), and each of the t transformations updates a fixed array of 26 letters. Space complexity remains O(26) because only the alphabet counts are stored.

Ready to solve this problem?

Practice Total Characters in String After Transformations I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters