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:
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".'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"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"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"bcabcdlm"Final Length of the string: The string is "bcabcdlm", which has 8 characters.
Constraints:
1 <= s.length <= 105s consists only of lowercase English letters.1 <= t <= 109nums.length == 261 <= nums[i] <= 25Problem 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.
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.
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.
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.
Java
JavaScript
Time Complexity: O(log t + n), where n is the length of the input string.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Direct Simulation of Transformations | Time Complexity: |
| Mathematical Calculation Without Simulation | Time Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation with Character Counting | O(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 |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,307 views views
Watch 9 more video solutions →Practice Total Characters in String After Transformations II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor