# Total Characters in String After Transformations I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/total-characters-in-string-after-transformations-i)
Canonical: https://scaleengineer.com/dsa/problems/total-characters-in-string-after-transformations-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## 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** `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`

# Approaches
## Brute-Force Simulation
The most straightforward approach is to directly simulate the transformation process. We can loop `t` times, and in each iteration, we build a new string by applying the transformation rules to every character of the current string. This method is easy to conceptualize but is highly impractical due to the potential for exponential growth in the string's length.
**Time:** O(t * L_avg) · **Space:** O(L_max)
**Pros:** Very simple to understand and implement.
**Cons:** Extremely inefficient in terms of both time and space.; The length of the string can grow exponentially, quickly exceeding memory limits (Memory Limit Exceeded).; Processing these very long strings at each step is very slow, leading to a timeout (Time Limit Exceeded).
### Explanation
This method involves a step-by-step simulation of the process described in the problem. We maintain the string as it transforms. For each of the `t` steps, we construct a new string based on the transformations of the characters in the previous string. 

For example, if `s = "az"` and `t = 1`:
1. We start with `"az"`.
2. We create a new empty string.
3. The first character `'a'` transforms to `'b'`. The new string is now `"b"`.
4. The second character `'z'` transforms to `"ab"`. The new string is now `"bab"`.
5. After one transformation, the result is `"bab"` and its length is 3.

While simple, this approach is not feasible for the given constraints because the string length can become enormous. If `s` contains many `'z'`s, the length can grow very rapidly. For instance, a single `'z'` becomes `"ab"` (length 2), which then becomes `"bc"` (length 2), then `"cd"` (length 2), and so on, until it becomes `"yz"` which transforms to `"z(ab)"`, resulting in `"zab"` (length 3). The growth becomes complex and leads to performance issues.

```java
// NOTE: This code is for illustrative purposes only and will fail due to TLE/MLE.
class Solution {
    public int totalCharacters(String s, int t) {
        String currentString = s;
        for (int i = 0; i < t; i++) {
            StringBuilder nextString = new StringBuilder();
            for (char c : currentString.toCharArray()) {
                if (c == 'z') {
                    nextString.append("ab");
                } else {
                    nextString.append((char)(c + 1));
                }
            }
            currentString = nextString.toString();
            // The string length can exceed memory limits here.
        }
        // The length can also exceed standard integer types.
        long length = currentString.length();
        int MOD = 1_000_000_007;
        return (int)(length % MOD);
    }
}
```
### Algorithm
- Start with the initial string `s`.
- Loop `t` times, representing each transformation.
- Inside the loop, create a new `StringBuilder` to build the string for the next state.
- Iterate through each character of the current string.
- If the character is `'z'`, append the string `"ab"` to the `StringBuilder`.
- Otherwise, append the next character in the alphabet (e.g., `'a'` becomes `'b'`).
- After iterating through all characters, replace the current string with the string generated by the `StringBuilder`.
- After `t` transformations, the length of the final string is the answer. Since the length can be very large, this approach is not practical.

## Dynamic Programming with Character Counts
A key observation is that we only need the *length* of the final string, not the string itself. The length is the sum of the counts of all characters. Instead of manipulating a potentially huge string, we can track the counts of each of the 26 lowercase letters. This turns the problem into a dynamic programming exercise where the state is the array of character counts.
**Time:** O(t * K) where K=26 · **Space:** O(K) where K=26
**Pros:** Very efficient in terms of space, using only a constant-size array.; Time complexity is linear with `t`, which is fast enough for the given constraints.; Avoids the memory and time overhead of string manipulation.
**Cons:** For extremely large values of `t` (larger than the problem constraints), this approach would be too slow.
### Explanation
We can define our state by a 26-element array, where each element `counts[i]` stores the number of occurrences of the `i`-th letter of the alphabet. We initialize this array based on the input string `s`.

Then, we simulate the process for `t` steps. In each step, we update the counts based on the transformation rules:
- A character `c` (where `c < 'z'`) becomes `c+1`. This means the count of `c+1` in the next step gets the count of `c` from the current step.
- A character `'z'` becomes `"ab"`. This means the count of `'a'` and `'b'` in the next step each get the count of `'z'` from the current step.

Let `counts_i` be the array of counts after `i` transformations. The transition is:
- `counts_{i+1}['a'] = counts_i['z']`
- `counts_{i+1}['b'] = counts_i['a'] + counts_i['z']`
- `counts_{i+1}[c] = counts_i[c-1]` for `c` from `'c'` to `'z'`.

We can implement this efficiently with an in-place update. After `t` steps, we sum up all the counts to find the total length.

```java
class Solution {
    public int totalCharacters(String s, int t) {
        int MOD = 1_000_000_007;
        long[] counts = new long[26];

        // 1. Initialize counts from the input string s
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }

        // 2. Perform t transformations
        for (int i = 0; i < t; i++) {
            long zCount = counts[25]; // Store count of 'z' before modification
            
            // Shift counts for 'b' through 'z'
            // 'y' -> 'z', 'x' -> 'y', ..., 'b' -> 'c'
            for (int j = 25; j >= 2; j--) {
                counts[j] = counts[j - 1];
            }
            
            // Update counts for 'a' and 'b'
            // 'a' -> 'b' and 'z' -> "ab"
            counts[1] = (counts[0] + zCount) % MOD;
            counts[0] = zCount;
        }

        // 3. Calculate total length
        long totalLength = 0;
        for (long count : counts) {
            totalLength = (totalLength + count) % MOD;
        }

        return (int) totalLength;
    }
}
```
### Algorithm
- Create a `long` array `counts` of size 26 to store the frequency of each character ('a' to 'z').
- Initialize `counts` by iterating through the input string `s`.
- Loop `t` times to simulate the transformations.
- In each iteration, calculate the counts for the next step based on the current counts:
  - Store the current count of `'z'` in a temporary variable, `zCount`.
  - The new count of `'z'` will be the old count of `'y'`. The new count of `'y'` will be the old count of `'x'`, and so on. This can be done by shifting the counts in the array: `counts[j] = counts[j-1]` for `j` from 25 down to 2.
  - The new count of `'b'` is the sum of the old count of `'a'` (which becomes `'b'`) and `zCount` (from `'z'` -> `"ab"`).
  - The new count of `'a'` is `zCount` (from `'z'` -> `"ab"`).
- All additions must be performed modulo `10^9 + 7`.
- After `t` iterations, sum all the values in the `counts` array to get the total length. Return this sum modulo `10^9 + 7`.

## Matrix Exponentiation
This approach elevates the dynamic programming solution by recognizing that the state transition is a linear transformation. Such transformations can be modeled using matrices. The state of character counts after `t` steps can be found by raising a transformation matrix `M` to the power of `t` and multiplying it by the initial state vector. The matrix power `M^t` can be computed very efficiently using binary exponentiation.
**Time:** O(K^3 * log t) where K=26 · **Space:** O(K^2) where K=26
**Pros:** Asymptotically the most efficient solution, with a logarithmic dependency on `t`.; A powerful and general technique for solving systems of linear recurrence relations.
**Cons:** Implementation is more complex than the DP approach, requiring functions for matrix multiplication and exponentiation.; The constant factor `K^3` is large, so for small `t`, the DP approach might be faster in practice.
### Explanation
Let `V_i` be a column vector of size 26 where `V_i[j]` is the count of the `j`-th character after `i` transformations. The transition `V_{i+1} = M * V_i` is defined by a 26x26 matrix `M`. After `t` steps, the final count vector will be `V_t = M^t * V_0`.

The core of this method is to first build the matrix `M` and then compute `M^t` in `O(K^3 * log t)` time, where `K=26`. This is significantly faster than the `O(t * K)` DP approach for large `t`.

**Matrix Construction:**
The matrix `M` is constructed as follows:
- `M[j+1][j] = 1` for `j` in `[0, 24]`: This maps `'a' -> 'b'`, `'b' -> 'c'`, etc.
- `M[0][25] = 1`: This maps `'z'` to the `'a'` in `"ab"`.
- `M[1][25] = 1`: This maps `'z'` to the `'b'` in `"ab"`.
- All other entries are 0.

Once we have `M^t`, we multiply it by the initial count vector `V_0` (derived from `s`) to get the final counts. The sum of these counts is our answer.

```java
class Solution {
    final int MOD = 1_000_000_007;
    final int K = 26;

    public int totalCharacters(String s, int t) {
        long[] v0 = new long[K];
        for (char c : s.toCharArray()) {
            v0[c - 'a']++;
        }

        if (t == 0) {
            return s.length();
        }

        long[][] M = new long[K][K];
        for (int i = 0; i < K - 1; i++) {
            M[i + 1][i] = 1; // 'a'->'b', 'b'->'c', ...
        }
        M[0][K - 1] = 1; // 'z' -> 'a'
        M[1][K - 1] = 1; // 'z' -> 'b'

        long[][] Mt = matrixPower(M, t);

        long[] vt = new long[K];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                vt[i] = (vt[i] + Mt[i][j] * v0[j]) % MOD;
            }
        }

        long totalLength = 0;
        for (long count : vt) {
            totalLength = (totalLength + count) % MOD;
        }

        return (int) totalLength;
    }

    private long[][] matrixMultiply(long[][] A, long[][] B) {
        long[][] C = new long[K][K];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                for (int l = 0; l < K; l++) {
                    C[i][j] = (C[i][j] + A[i][l] * B[l][j]) % MOD;
                }
            }
        }
        return C;
    }

    private long[][] matrixPower(long[][] A, int n) {
        long[][] res = new long[K][K];
        for (int i = 0; i < K; i++) {
            res[i][i] = 1; // Identity matrix
        }
        long[][] P = A;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = matrixMultiply(res, P);
            }
            P = matrixMultiply(P, P);
            n >>= 1;
        }
        return res;
    }
}
```
### Algorithm
- Represent the character counts as a 26x1 column vector `V`.
- The transformation from one step to the next is a linear operation, which can be represented by a 26x26 matrix `M`. `V_{i+1} = M * V_i`.
- Construct the transformation matrix `M` based on the rules:
  - For `j` from 0 to 24, `M[j+1][j] = 1` (representing `char(j)` -> `char(j+1)`).
  - `M[0][25] = 1` and `M[1][25] = 1` (representing `'z'` -> `"ab"`).
- The count vector after `t` steps is `V_t = M^t * V_0`, where `V_0` is the initial count vector from string `s`.
- Calculate `M^t` efficiently using binary exponentiation (also known as exponentiation by squaring). This involves `O(log t)` matrix multiplications.
- Multiply the resulting `M^t` matrix by the initial count vector `V_0` to get the final count vector `V_t`.
- Sum the elements of `V_t` to get the total length, taking the result modulo `10^9 + 7`.

# Solutions
### Java

```java
class Solution {
public
  int lengthAfterTransformations(String s, int t) {
    final int mod = (int)1 e9 + 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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```