3629. Total Characters In String After Transformations I¶

3629. Total Characters in String After Transformations I

Medium

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 modulo 109 + 7.

Example 1:

Example 2:

Constraints:

• 1 <= s.length <= 105
• s consists only of lowercase English letters.
• 1 <= t <= 105

Solution¶

class Solution {
    static int MOD = (int)(1e9 + 7);
    public int lengthAfterTransformations(String s, int t) {
        int n = s.length();
        int res = 0;
        int freq[] = new int[26];
        for (int i = 0; i < n; i++) freq[s.charAt(i) - 'a']++;
        while (t-->0) {
            int zCount = freq[25];
            for (int i = 24; i >= 0; i--) {
                freq[i + 1] = freq[i];
                freq[i] = 0;
            }
            if (zCount > 0) {
                freq[0] = (freq[0] + zCount) % MOD;
                freq[1] = (freq[1] + zCount) % MOD;
            }
        }
        for (int ele : freq) res = (res + ele) % MOD;
        return res;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]