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". Oth

lengthAfterTransformations.js

/**
 * @param {string} s
 * @param {number} t
 * @return {number}
 */
var lengthAfterTransformations = function(s, t) {
    const MOD = 1000000007;
    const n = s.length;

    // Step 1: Count occurrences of each character in 's'
    const charCounts = {};
    for (const char of s) {
        charCounts[char] = (charCounts[char] || 0) + 1;
    }

    // If no transformations are applied, return the original length
    if (t === 0) {
        return n;
    }

    // Step 2: Initialize DP array
    // dp[i][j] represents how characters evolve over j transformations
    const dp = Array(26).fill(0).map(() => Array(t + 1).fill(0));

    // Base case: At t=0, each character maintains itself
    for (let i = 0; i < 26; i++) {
        dp[i][0] = 1;
    }

    // Step 3: Fill DP table for transformations
    for (let j = 1; j <= t; j++) {
        for (let i = 0; i < 25; i++) {
            dp[i][j] = dp[i + 1][j - 1];  // Characters shift forward
        }
        dp[25][j] = (dp[0][j - 1] + dp[1][j - 1]) % MOD; // 'z' expands into "ab"
    }

    // Step 4: Compute final length based on character frequencies
    let result = 0;
    for (const char in charCounts) {
        const charCode = char.charCodeAt(0) - 'a'.charCodeAt(0);
        const frequency = charCounts[char];

        // Calculate contribution of each character using DP table
        result = (result + (dp[charCode][t] * frequency) % MOD) % MOD;
    }

    return result;
};