Total Characters in String After Transformations I

Leetcode Problem:

• Total Characters in String After Transformations I

Summary

• Find the length of the resulting string after t transformations on a given string s, where each transformation replaces 'z' with 'ab' and other characters with the next character in the alphabet.

Approach

• The solution uses a dynamic programming approach to calculate the length of the resulting string
• It first counts the occurrences of each character in the string, then iterates t times, updating the counts based on the transformation rules
• Finally, it calculates the total length of the resulting string by summing up the counts.

Complexity

• O(t * 26) where t is the number of transformations and 26 is the number of characters in the alphabet

Explanation

• The solution starts by counting the occurrences of each character in the string
• It then iterates t times, updating the counts based on the transformation rules
• If the current character is 'z', it increments the counts for 'a' and 'b'
• Otherwise, it increments the count for the next character in the alphabet
• Finally, it calculates the total length of the resulting string by summing up the counts.

Solution Code:

const int mod = 1e9 + 7;
int mod_add(int a, int b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;}

class Solution {
public:
    int lengthAfterTransformations(string s, int t) {
        int nums[26] = {0};
        for (char ch : s) nums[ch - 'a']++;
        while (t--) {
            int cur[26] = {0};
            for (int j = 0; j < 26; j++) {
                if (j == 25 && nums[j] > 0) {
                    cur[0] = mod_add(cur[0], nums[j]);
                    cur[1] = mod_add(cur[1], nums[j]);
                } else {
                    if (j < 25) cur[j + 1] = mod_add(cur[j + 1], nums[j]);
                }
            }
            for (int j = 0; j < 26; j++) nums[j] = cur[j];
        }
        int ans = 0;
        for (int i : nums) ans = mod_add(ans, i);
        return (int)ans;
    }
};