Problem

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

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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.

Constraints:

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

Solution

Method 1 - Using Maths

Here is the approach:

  • Use an array (cnt) to represent the count of each letter ('a' → cnt[0], 'b' → cnt[1], …, 'z' → cnt[25]).
  • For each transformation:
    • 'z' contributes to 'a' and 'b'.
    • All other characters shift to the next one (e.g., 'a' contributes to 'b', 'b' contributes to 'c', etc.).
  • After t transformations, sum up all counts modulo 10^9 + 7 to compute the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Solution {

    private static final int MOD = 1_000_000_007;

    public int lengthAfterTransformations(String s, int t) {
        int[] cnt = new int[26]; // Array to count occurrences of each character
        
        // Initialize the count array
        for (char ch : s.toCharArray()) {
            ++cnt[ch - 'a'];
        }
        
        // Perform t transformations
        for (int round = 0; round < t; ++round) {
            int[] nxt = new int[26]; // Temporary array to store new counts
            
            // 'z' transitions into 'a' and 'b'
            nxt[0] = cnt[25];
            nxt[1] = (cnt[25] + cnt[0]) % MOD;
            
            // Characters 'a' to 'y' transition normally
            for (int i = 2; i < 26; ++i) {
                nxt[i] = cnt[i - 1];
            }
            
            cnt = nxt; // Update counts
        }
        
        // Sum up all counts modulo MOD
        int ans = 0;
        for (int count : cnt) {
            ans = (ans + count) % MOD;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    MOD: int = 10**9 + 7  # Define the modulo constant

    def length_after_transformations(self, s: str, t: int) -> int:
        cnt = [0] * 26  # Array to count occurrences of each character
        
        # Initialize the count array
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1
        
        # Perform t transformations
        for _ in range(t):
            nxt = [0] * 26  # Temporary array to store new counts
            
            # 'z' transitions into 'a' and 'b'
            nxt[0] = cnt[25]
            nxt[1] = (cnt[25] + cnt[0]) % self.MOD
            
            # Characters 'a' to 'y' transition normally
            for i in range(2, 26):
                nxt[i] = cnt[i - 1]
            
            cnt = nxt  # Update counts
        
        # Sum up all counts modulo MOD
        return sum(cnt) % self.MOD

Complexity

  • ⏰ Time complexity: O(t). The algorithm processes 26 characters for each of the t transformations, making it O(26 * t) => O(t).
  • 🧺 Space complexity: O(1). The space usage is constant at O(26) for the cnt and nxt arrays.