Skip to main content
Talentd

Total Characters in String After Transformations II - Solution & Explanation

HardHash TableMathStringDynamic Programming15 min readAsked at: Meta, Google
Practice this problem

Problem Statement

You are given a string s consisting of lowercase English letters, an integer t representing the number of transformations to perform, and an array nums of size 26. In one transformation, every character in s is replaced according to the following rules:

  • Replace s[i] with the next nums[s[i] - 'a'] consecutive characters in the alphabet. For example, if s[i] = 'a' and nums[0] = 3, the character 'a' transforms into the next 3 consecutive characters ahead of it, which results in "bcd".
  • The transformation wraps around the alphabet if it exceeds 'z'. For example, if s[i] = 'y' and nums[24] = 3, the character 'y' transforms into the next 3 consecutive characters ahead of it, which results in "zab".

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, nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]

Output: 7

Explanation:

  • First Transformation (t = 1):

    • 'a' becomes 'b' as nums[0] == 1
    • 'b' becomes 'c' as nums[1] == 1
    • 'c' becomes 'd' as nums[2] == 1
    • 'y' becomes 'z' as nums[24] == 1
    • 'y' becomes 'z' as nums[24] == 1
    • String after the first transformation: "bcdzz"

  • Second Transformation (t = 2):

    • 'b' becomes 'c' as nums[1] == 1
    • 'c' becomes 'd' as nums[2] == 1
    • 'd' becomes 'e' as nums[3] == 1
    • 'z' becomes 'ab' as nums[25] == 2
    • 'z' becomes 'ab' as nums[25] == 2
    • 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, nums = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]

Output: 8

Explanation:

  • First Transformation (t = 1):

    • 'a' becomes 'bc' as nums[0] == 2
    • 'z' becomes 'ab' as nums[25] == 2
    • 'b' becomes 'cd' as nums[1] == 2
    • 'k' becomes 'lm' as nums[10] == 2
    • String after the first transformation: "bcabcdlm"

  • Final Length of the string: The string is "bcabcdlm", which has 8 characters.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists only of lowercase English letters.
  • 1 <= t <= 109
  • nums.length == 26
  • 1 <= nums[i] <= 25

Approach Overview

Problem Overview: You start with a string s. Each transformation step changes every character according to predefined rules, potentially expanding one character into multiple new characters. After applying the transformation t times, return the total number of characters in the final string. Directly building the string quickly becomes impossible because its size grows exponentially.

Approach 1: Direct Simulation of Transformations (Counting DP) (Time: O(t * 26), Space: O(26))

Instead of constructing the full string, track how many times each character appears. Use a frequency array of size 26 where freq[i] represents the count of the i-th letter. For each transformation step, compute a new frequency array based on how each character expands according to the rules. This avoids large string allocations and turns the process into simple counting updates. The algorithm iterates through all 26 characters per step and accumulates counts. This approach works well when t is relatively small and is easy to implement using arrays or a hash table style frequency map.

Approach 2: Mathematical Calculation Without Simulation (Matrix / Transition DP) (Time: O(26^3 log t), Space: O(26^2))

When t is very large, even iterating t times becomes too slow. Model the transformation rules as a transition matrix where M[i][j] represents how many characters of type j are produced from character i in one step. The state vector contains counts of each letter. Applying a transformation becomes a matrix multiplication: next = current × M. Repeating the transformation t times becomes matrix exponentiation: M^t. Fast exponentiation reduces the runtime to logarithmic in t. This approach relies on mathematical modeling and dynamic programming style state transitions.

Recommended for interviews: Start with the counting simulation. It shows that you recognized the exponential growth problem and replaced string construction with frequency tracking. For large constraints, interviewers expect the mathematical transition approach using matrix exponentiation. That solution demonstrates deeper understanding of state transitions, repeated transformations, and optimization techniques used in advanced dynamic programming problems.

Approach 1: Direct Simulation of Transformations

This approach involves directly simulating each transformation step-by-step. For each character in the string, determine the next characters it transforms into based on the nums array. Repeat this process t times and calculate the length of the resulting string.

This approach, while straightforward, can quickly become computationally expensive as the length of the string grows exponentially with each transformation, especially for large values of t.

The function total_transformed_length takes a string s, the number of transformations t, and an array nums. It calculates the length of the resulting string after t transformations. The length is computed by summing up the transformation length for each character in the string and is returned modulo 10^9 + 7.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(t * n), where n is the length of the string s.
Space Complexity: O(1), as we only store a few variables for computation.

Try this approach in the editor →

Approach 2: Mathematical Calculation Without Simulation

Instead of simulating each transformation, consider calculating how the length changes character by character and accumulate the total transformation effect. The transformation sequence is uniform, and we can calculate the total theoretical length in one go using matrix exponentiation or pre-computed powers.

This approach directly calculates the expected length based on fixed relationship assumptions, avoiding direct string manipulations and reducing computational complexity significantly.

The method totalTransformedLength calculates the product of transformation lengths raised to the power of t using quick powering technique (fastPower), thereby efficiently computing the final length without simulating each transformation.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(log t + n), where n is the length of the input string.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Fast Matrix Exponentiation to Accelerate Recurrence

We define f[i][j] as the number of times the j-th letter appears in the alphabet after i transformations. Initially, f[0][j] corresponds to the frequency of the j-th letter in the input string s.

Since the frequency of each letter after a transformation affects the next transformation, and the total number of transformations t can be large, we can accelerate this recurrence process using fast matrix exponentiation.

Note that the result can be very large, so we take modulo 10^9 + 7.

The time complexity of this approach is O(n + log t times |\Sigma|^3), where n is the length of the string and |\Sigma| is the size of the alphabet (in this case, 26). The space complexity is O(|\Sigma|^2), which is the size of the matrix used for matrix multiplication.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Simulation of Transformations

Time Complexity: O(t * n), where n is the length of the string s.
Space Complexity: O(1), as we only store a few variables for computation.

Mathematical Calculation Without Simulation

Time Complexity: O(log t + n), where n is the length of the input string.
Space Complexity: O(1).

Fast Matrix Exponentiation to Accelerate Recurrence—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation with Character CountingO(t * 26)O(26)When transformation count t is moderate and a straightforward DP approach is sufficient
Mathematical Transition Matrix (Matrix Exponentiation)O(26^3 log t)O(26^2)When t is extremely large and repeated transformations must be computed efficiently

Video Solution

Total Characters in String After Transformations II | Matrix Exponentiation | Leetcode 3337 • Techdose • 6,424 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Total Characters in String After Transformations II easy or hard?
The problem is categorized as Hard because the naive approach quickly becomes infeasible due to exponential growth of the string. Recognizing the need for frequency counting or matrix exponentiation is the key difficulty.
Total Characters in String After Transformations II Python/Java solution
Python and C++ implementations often use the direct counting simulation with arrays for clarity. Java and JavaScript solutions typically implement the mathematical optimization with matrix exponentiation to efficiently handle large numbers of transformations.
How to solve Total Characters in String After Transformations II in O(log t)?
Represent the transformation rules as a 26×26 transition matrix. Raise this matrix to the power t using fast exponentiation, then multiply it with the initial frequency vector of the string. This computes the final character counts in logarithmic time relative to the number of transformations.
What is the best approach for Total Characters in String After Transformations II?
The most efficient approach models character transformations as a transition matrix and applies matrix exponentiation. This reduces repeated transformations from O(t) iterations to O(log t) matrix multiplications. It works by tracking how each letter contributes to others over time using a 26×26 matrix.
Is Total Characters in String After Transformations II asked at Google/Amazon/Meta?
Problems involving transformation rules, frequency counting, and matrix exponentiation commonly appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test dynamic programming, mathematical modeling, and optimization of repeated operations.
What data structure is used in Total Characters in String After Transformations II?
The core structure is a fixed-size frequency array of length 26 to track counts of lowercase letters. Advanced solutions also use a 26×26 matrix to represent character transitions, combined with fast exponentiation algorithms.
What is the time complexity of Total Characters in String After Transformations II?
The counting simulation approach runs in O(t * 26) time and O(26) space by updating character frequencies each step. The optimized mathematical approach uses matrix exponentiation with O(26^3 log t) time and O(26^2) space.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters