Skip to content

3335. Total Characters in String After Transformations I

Description

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:

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.

 

Constraints:

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

Solutions

Solution 1: Recurrence

Thinking

Each step shifts a letter forward, and \(\texttt{z}\) becomes \(\texttt{ab}\). With \(t \le 10^5\) we cannot rewrite the string.

Only the \(26\) letter counts matter. \(f[i][j]\) is the count of letter \(j\) after \(i\) steps: \(\texttt{z}\) feeds \(\texttt{a}\) and \(\texttt{b}\), and every other letter comes from the previous one.

The answer is the sum of \(f[t]\), taken modulo \(10^9+7\).

We define \(f[i][j]\) to represent the count of the \(j\)-th letter in the alphabet after \(i\) transformations. Initially, \(f[0][j]\) is the count of the \(j\)-th letter in the string \(s\).

After each transformation, the count of the \(j\)-th letter in the alphabet can be calculated as follows:

\[ \begin{align*} f[i][0] &= f[i - 1][25] \\ f[i][1] &= f[i - 1][0] + f[i - 1][25] \\ f[i][2] &= f[i - 1][1] \\ f[i][3] &= f[i - 1][2] \\ &\vdots \\ f[i][25] &= f[i - 1][24] \end{align*} \]

The answer is \(f[t][0] + f[t][1] + \ldots + f[t][25]\).

Since the answer can be very large, we take the result modulo \(10^9 + 7\).

The time complexity is \(O(t \times |\Sigma|)\), and the space complexity is \(O(t \times |\Sigma|)\), where \(|\Sigma|\) is the size of the alphabet.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        f = [[0] * 26 for _ in range(t + 1)]
        for c in s:
            f[0][ord(c) - ord("a")] += 1
        for i in range(1, t + 1):
            f[i][0] = f[i - 1][25]
            f[i][1] = f[i - 1][0] + f[i - 1][25]
            for j in range(2, 26):
                f[i][j] = f[i - 1][j - 1]
        mod = 10**9 + 7
        return sum(f[t]) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int lengthAfterTransformations(String s, int t) {
        final int mod = (int) 1e9 + 7;
        int[][] f = new int[t + 1][26];
        for (char c : s.toCharArray()) {
            f[0][c - 'a']++;
        }
        for (int i = 1; i <= t; ++i) {
            f[i][0] = f[i - 1][25] % mod;
            f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
            for (int j = 2; j < 26; j++) {
                f[i][j] = f[i - 1][j - 1] % mod;
            }
        }

        int ans = 0;
        for (int j = 0; j < 26; ++j) {
            ans = (ans + f[t][j]) % 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 {
public:
    int lengthAfterTransformations(string s, int t) {
        const int mod = 1e9 + 7;
        vector<vector<int>> f(t + 1, vector<int>(26, 0));

        for (char c : s) {
            f[0][c - 'a']++;
        }

        for (int i = 1; i <= t; ++i) {
            f[i][0] = f[i - 1][25] % mod;
            f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
            for (int j = 2; j < 26; ++j) {
                f[i][j] = f[i - 1][j - 1] % mod;
            }
        }

        int ans = 0;
        for (int j = 0; j < 26; ++j) {
            ans = (ans + f[t][j]) % 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
func lengthAfterTransformations(s string, t int) int {
    const mod = 1_000_000_007
    f := make([][]int, t+1)
    for i := range f {
        f[i] = make([]int, 26)
    }

    for _, c := range s {
        f[0][c-'a']++
    }

    for i := 1; i <= t; i++ {
        f[i][0] = f[i-1][25] % mod
        f[i][1] = (f[i-1][0] + f[i-1][25]) % mod
        for j := 2; j < 26; j++ {
            f[i][j] = f[i-1][j-1] % mod
        }
    }

    ans := 0
    for j := 0; j < 26; j++ {
        ans = (ans + f[t][j]) % 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
function lengthAfterTransformations(s: string, t: number): number {
    const mod = 1_000_000_007;
    const f: number[][] = Array.from({ length: t + 1 }, () => Array(26).fill(0));

    for (const c of s) {
        f[0][c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    for (let i = 1; i <= t; i++) {
        f[i][0] = f[i - 1][25] % mod;
        f[i][1] = (f[i - 1][0] + f[i - 1][25]) % mod;
        for (let j = 2; j < 26; j++) {
            f[i][j] = f[i - 1][j - 1] % mod;
        }
    }

    let ans = 0;
    for (let j = 0; j < 26; j++) {
        ans = (ans + f[t][j]) % mod;
    }

    return ans;
}

Comments