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 modulo10^9 + 7.

LeetCode

• https://leetcode.com/problems/total-characters-in-string-after-transformations-i/description/

Constraints

1 <= s.length <= 10^5
s consists only of lowercase English letters.
1 <= t <= 10^5

• 1 ≤ s.length ≤ 10^5
  • The length of string s can be up to 100,000 characters.
    • Since the length can be up to 10^5, you cannot afford O(n^2) (quadratic) time complexity – it will timeout (TLE).
    • You should aim for:
      • O(n) linear
      • O(n log n) linearithmic
      • or at most O(k * n) where k is small (e.g., 26 for lowercase characters)
• s consists of only lowercase english letters:
  • There are only 26 unique characters to consider.
• 1 ≤ t ≤ 10^5

Examples

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.

Different Approaches

1️⃣ Brute Force Approach

Idea:

Try all transformation

Code:

class Solution {
public:
    // This function applies a transformation `t` times on string `s`
    // and returns the final length of the transformed string.
    int lengthAfterTransformations(string s, int t) {
        // Repeat the transformation `t` times
        for (int round = 0; round < t; round++) {
            string transformedString = "";

            // Go through each character in the current string
            for (char currentChar : s) {
                // If the character is 'z', replace it with "ab"
                if (currentChar == 'z') {
                    transformedString += "ab";
                } else {
                    // Otherwise, increment the character by one in the alphabet
                    // For example, 'a' becomes 'b', 'b' becomes 'c', ..., 'y' becomes 'z'
                    transformedString += currentChar + 1;
                }
            }

            // Update the original string with the new transformed version
            s = transformedString;
        }

        // Return the length of the final string after all transformations
        return s.size();
    }
};

Complexity Analysis:

• Time Complexity:O(n * 2 ^ t)
  • At each transformation round, you go through every character in the string and possibly increase the length.
  • Worst case: All characters are z.
    • In each round, every z becomes ab – string length doubles
    • So after t rounds, length becomes O(n * 2 ^ t)
• Space Complexity:O(n × 2^t)
  • You create a new string temp in each round (of length up to n × 2^t in the worst case).

2️⃣ Better Approach

Code:

class Solution {
public:
    // A constant MOD value to prevent integer overflow in large calculations
    static constexpr int MOD = 1'000'000'007;

    // Function to compute the length of the string after 't' transformations
    int lengthAfterTransformations(string s, int t) {
        // Step 1: Create a frequency map of characters in the input string
        unordered_map<char, int> charFrequency;

        for (char ch : s) {
            charFrequency[ch]++;
        }

        // Step 2: Apply transformations for 't' rounds
        for (int i = 0; i < t; i++) {
            // Temporary map to store updated character frequencies after this round
            unordered_map<char, int> tempFrequency;

            // Traverse through current frequency map
            for (auto entry : charFrequency) {
                char ch = entry.first;
                int count = entry.second;

                // If the character is not 'z', simply increment the character
                if (ch != 'z') {
                    tempFrequency[ch + 1] = (tempFrequency[ch + 1] + count) % MOD;
                }
                // If the character is 'z', replace it with "ab"
                else {
                    tempFrequency['a'] = (tempFrequency['a'] + count) % MOD;
                    tempFrequency['b'] = (tempFrequency['b'] + count) % MOD;
                }
            }

            // Move updated frequencies to the main map for the next round
            charFrequency = move(tempFrequency);
        }

        // Step 3: Compute the total number of characters after all transformations
        int finalLength = 0;
        for (auto entry : charFrequency) {
            finalLength = (finalLength + entry.second) % MOD;
        }

        return finalLength;
    }
};

Complexity Analysis:

3️⃣ Optimized Approach

Code:

class Solution {
public:
    // Constant to take modulo and prevent overflow on large counts
    static constexpr int MOD = 1'000'000'007;

    // Function to return the length of the string after `t` transformations
    int lengthAfterTransformations(string s, int t) {
        // Step 1: Create a frequency array for all lowercase letters (a-z)
        // Index 0 for 'a', 1 for 'b', ..., 25 for 'z'
        vector<int> frequency(26, 0);

        // Count initial frequency of each character in the string
        for (char ch : s) {
            frequency[ch - 'a']++;
        }

        // Step 2: Apply `t` rounds of transformation
        for (int i = 0; i < t; i++) {
            // Create a new frequency array for this round
            vector<int> tempFrequency(26, 0);

            // Iterate through each character a to z (represented as index 0 to 25)
            for (int idx = 0; idx < 26; idx++) {
                int count = frequency[idx];       // Count of current character
                char ch = idx + 'a';              // Convert index back to character

                if (ch != 'z') {
                    // If current character is not 'z', increment the character
                    // For example, 'a' becomes 'b', 'b' becomes 'c', etc.
                    tempFrequency[ch + 1 - 'a'] = (tempFrequency[ch + 1 - 'a'] + count) % MOD;
                } else {
                    // Special case: if character is 'z', it becomes "ab"
                    tempFrequency['a' - 'a'] = (tempFrequency['a' - 'a'] + count) % MOD;
                    tempFrequency['b' - 'a'] = (tempFrequency['b' - 'a'] + count) % MOD;
                }
            }

            // Move new frequencies to the main array for the next round
            frequency = move(tempFrequency);
        }

        // Step 3: Calculate the final string length
        int totalLength = 0;
        for (int i = 0; i < 26; i++) {
            totalLength = (totalLength + frequency[i]) % MOD;
        }

        return totalLength;
    }
};

Complexity Analysis:

• Time Complexity:O(t)
  • Each transformation step runs in O(26)
  • Total time for t transformations: O(26 * t) = O(t)
• Space Complexity:O(1)
  • Uses two fixed-size arrays of 26 elements.