# Total Characters in String After Transformations II
**Difficulty:** HARD
[External](https://leetcode.com/problems/total-characters-in-string-after-transformations-ii)
Canonical: https://scaleengineer.com/dsa/problems/total-characters-in-string-after-transformations-ii
**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` consisting of lowercase English letters, an integer `t` representing the number of **transformations** to perform, and an array `nums` of size 26\. In one **transformation**, every character in `s` is replaced according to the following rules:

* Replace `s[i]` with the **next** `nums[s[i] - 'a']` consecutive characters in the alphabet. For example, if `s[i] = 'a'` and `nums[0] = 3`, the character `'a'` transforms into the next 3 consecutive characters ahead of it, which results in `"bcd"`.
* The transformation **wraps** around the alphabet if it exceeds `'z'`. For example, if `s[i] = 'y'` and `nums[24] = 3`, the character `'y'` transforms into the next 3 consecutive characters ahead of it, which results in `"zab"`.

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, nums = \[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2\]

**Output:** 7

**Explanation:**

* **First Transformation (t = 1):**

  * `'a'` becomes `'b'` as `nums[0] == 1`
  * `'b'` becomes `'c'` as `nums[1] == 1`
  * `'c'` becomes `'d'` as `nums[2] == 1`
  * `'y'` becomes `'z'` as `nums[24] == 1`
  * `'y'` becomes `'z'` as `nums[24] == 1`
  * String after the first transformation: `"bcdzz"`
* **Second Transformation (t = 2):**

  * `'b'` becomes `'c'` as `nums[1] == 1`
  * `'c'` becomes `'d'` as `nums[2] == 1`
  * `'d'` becomes `'e'` as `nums[3] == 1`
  * `'z'` becomes `'ab'` as `nums[25] == 2`
  * `'z'` becomes `'ab'` as `nums[25] == 2`
  * 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, nums = \[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2\]

**Output:** 8

**Explanation:**

* **First Transformation (t = 1):**

  * `'a'` becomes `'bc'` as `nums[0] == 2`
  * `'z'` becomes `'ab'` as `nums[25] == 2`
  * `'b'` becomes `'cd'` as `nums[1] == 2`
  * `'k'` becomes `'lm'` as `nums[10] == 2`
  * String after the first transformation: `"bcabcdlm"`
* **Final Length of the string:** The string is `"bcabcdlm"`, which has 8 characters.

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists only of lowercase English letters.
* `1 <= t <= 109`
* `nums.length == 26`
* `1 <= nums[i] <= 25`

# Approaches
## Brute Force Simulation
This approach directly simulates the transformation process as described in the problem. It starts with the initial string `s` and, for `t` times, generates a new string by replacing each character of the current string with its corresponding transformation.
**Time:** O(t * L_avg * max(nums)), where `L_avg` is the average length of the string across transformations. Since the length can grow exponentially, this is infeasible. · **Space:** O(L_max), where `L_max` is the maximum length of the string, which can be huge.
**Pros:** Simple to understand and implement.; Directly follows the problem description.
**Cons:** Extremely inefficient for large `t` as it requires `t` iterations.; The string length can grow exponentially, leading to Memory Limit Exceeded.; String concatenations in a loop are slow, leading to Time Limit Exceeded.
### Explanation
The algorithm iterates `t` times. In each iteration, it constructs a new string. It traverses the current string character by character. For each character `c`, it determines the sequence of new characters based on `nums[c - 'a']`. The new characters are `(c+1)%26`, `(c+2)%26`, etc., wrapping around the alphabet from 'z' to 'a'. These new characters are appended to a temporary string builder. After iterating through all characters of the current string, the temporary string builder's content becomes the new current string for the next iteration. This process is repeated `t` times. Finally, the length of the resulting string is returned. Due to the potentially massive growth in string length and the large value of `t`, this approach is extremely slow and memory-intensive. It's not feasible for the given constraints and will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) errors.

```java
// This is a conceptual implementation and will not pass due to performance issues.
public int totalCharacters(String s, int t, int[] nums) {
    String currentString = s;
    for (int i = 0; i < t; i++) {
        StringBuilder nextString = new StringBuilder();
        for (char c : currentString.toCharArray()) {
            int len = nums[c - 'a'];
            for (int j = 1; j <= len; j++) {
                char nextChar = (char) ('a' + (c - 'a' + j) % 26);
                nextString.append(nextChar);
            }
        }
        currentString = nextString.toString();
        // The length can exceed memory limits long before t iterations.
    }
    return currentString.length(); // Modulo arithmetic is omitted for clarity of the basic idea.
}
```
### Algorithm
1. Initialize `currentString = s`.
2. Loop `t` times (from 1 to `t`):
    a. Create an empty `StringBuilder` called `nextString`.
    b. For each character `c` in `currentString`:
        i. Get the transformation length `k = nums[c - 'a']`.
        ii. For `j` from 1 to `k`:
            - Calculate the next character: `nextChar = 'a' + ((c - 'a' + j) % 26)`.
            - Append `nextChar` to `nextString`.
    c. Update `currentString = nextString.toString()`.
3. Return `currentString.length()`.

## Iterative Simulation with Character Counts
This approach improves upon the brute-force method by avoiding the construction of the actual strings. Instead, it keeps track of the frequency of each character ('a' through 'z') in the string. The transformation is simulated by updating these counts for `t` iterations.
**Time:** O(s.length() + t * 26 * max(nums)). Since `max(nums)` is at most 25, this simplifies to `O(s.length() + t)`. This will cause a Time Limit Exceeded error for large `t`. · **Space:** O(1), as we only use a few arrays of size 26.
**Pros:** Avoids large string manipulation, significantly reducing memory usage.; Space complexity is constant.
**Cons:** The time complexity is linear in `t`, which is too slow for `t` up to 10^9.
### Explanation
We only need the length of the final string, which is the sum of character counts. The actual string sequence is irrelevant. We start by creating a frequency map (an array of size 26) for the initial string `s`. `counts[i]` will store the number of occurrences of character `'a' + i`. Then, we simulate the `t` transformations. In each step, we create a new frequency map `next_counts` for the next state, initialized to all zeros. We iterate through the current `counts` array. For each character `'a' + i` with a count `counts[i] > 0`, we determine its transformation. The character `'a' + i` transforms into `nums[i]` new characters. For each of these new characters, say `'a' + j`, we add `counts[i]` to `next_counts[j]`. After processing all 26 character types, `next_counts` becomes the new `counts` for the next iteration. All calculations are performed modulo `10^9 + 7` to prevent overflow. After `t` iterations, we sum up all values in the final `counts` array to get the total length. This approach is much better in terms of memory but is still too slow because `t` can be up to 10^9.

```java
public int totalCharacters(String s, int t, int[] nums) {
    long MOD = 1000000007;
    long[] counts = new long[26];
    for (char c : s.toCharArray()) {
        counts[c - 'a']++;
    }

    for (int step = 0; step < t; step++) {
        long[] nextCounts = new long[26];
        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0) {
                int len = nums[i];
                for (int j = 1; j <= len; j++) {
                    int nextCharIndex = (i + j) % 26;
                    nextCounts[nextCharIndex] = (nextCounts[nextCharIndex] + counts[i]) % MOD;
                }
            }
        }
        counts = nextCounts;
    }

    long totalLength = 0;
    for (long count : counts) {
        totalLength = (totalLength + count) % MOD;
    }
    return (int) totalLength;
}
```
### Algorithm
1. Initialize a `long` array `counts` of size 26 to all zeros.
2. For each character `c` in `s`, increment `counts[c - 'a']`.
3. Define `MOD = 10^9 + 7`.
4. Loop `t` times:
    a. Create a new `long` array `next_counts` of size 26, initialized to zeros.
    b. For `i` from 0 to 25:
        i. If `counts[i] > 0`:
            - Let `k = nums[i]`.
            - For `j` from 1 to `k`:
                - `next_char_index = (i + j) % 26`.
                - `next_counts[next_char_index] = (next_counts[next_char_index] + counts[i]) % MOD`.
    c. Replace `counts` with `next_counts`.
5. Calculate the total length by summing all elements in `counts` modulo `MOD`.
6. Return the total length.

## Matrix Exponentiation
This is the most efficient approach, leveraging linear algebra. The transformation of character counts from one step to the next can be modeled as a matrix-vector multiplication. By representing the transformation as a matrix, we can use binary exponentiation (also known as exponentiation by squaring) to compute the result of `t` transformations in logarithmic time with respect to `t`.
**Time:** O(s.length() + 26^3 * log t). The `s.length()` part is for initial counting. The `26^3 * log t` part is for matrix exponentiation. Both parts are well within time limits. · **Space:** O(26^2) or O(1), for storing the matrices.
**Pros:** Highly efficient for large `t` due to logarithmic time complexity with respect to `t`.; Handles the constraints of the problem effectively.; A standard and powerful technique for problems involving linear recurrences or state transitions.
**Cons:** More complex to understand and implement compared to simulation.; The constant factor in the time complexity (`26^3`) is significant, though acceptable for this problem.
### Explanation
Let `C_k` be a 26x1 column vector where `C_k[i]` is the count of character `'a' + i` after `k` transformations. The transition from `C_k` to `C_{k+1}` is a linear transformation: `C_{k+1} = M * C_k`, where `M` is a 26x26 transformation matrix. The matrix `M` is constructed such that `M[j][i]` is the number of times character `'a' + j` is produced from a single character `'a' + i`. In this problem, this value is either 0 or 1. Specifically, `M[j][i] = 1` if `'a' + j` is in the transformed string of `'a' + i`, and 0 otherwise. After `t` transformations, the final count vector is `C_t = M^t * C_0`, where `C_0` is the initial count vector from string `s`. We can compute `M^t` efficiently in `O(26^3 * log t)` time using binary exponentiation for matrices. The overall algorithm is to compute `C_0`, construct `M`, compute `M^t`, find `C_t`, and sum its elements.

```java
class Solution {
    long MOD = 1000000007;
    int SIZE = 26;

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

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

        long[][] transformMatrix = new long[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            int len = nums[i];
            for (int j = 1; j <= len; j++) {
                transformMatrix[(i + j) % SIZE][i] = 1;
            }
        }

        long[][] finalTransformMatrix = matrixPower(transformMatrix, t);

        long[] finalCounts = new long[SIZE];
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                finalCounts[i] = (finalCounts[i] + finalTransformMatrix[i][j] * initialCounts[j]) % MOD;
            }
        }

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

        return (int) totalLength;
    }

    private long[][] matrixPower(long[][] base, long exp) {
        long[][] result = new long[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            result[i][i] = 1; // Identity matrix
        }
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = multiply(result, base);
            }
            base = multiply(base, base);
            exp /= 2;
        }
        return result;
    }

    private long[][] multiply(long[][] a, long[][] b) {
        long[][] result = new long[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                for (int k = 0; k < SIZE; k++) {
                    result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
1. Define `MOD = 10^9 + 7`.
2. Create the initial count vector `C_0` (a `long[26]` array) from `s`.
3. Create the transformation matrix `M` (a `long[26][26]` array).
    - For `i` from 0 to 25:
        - Let `k = nums[i]`.
        - For `j` from 1 to `k`:
            - `M[(i + j) % 26][i] = 1`.
4. Implement a function `matrixPower(matrix, power)` that computes `matrix^power` using binary exponentiation.
    - It should handle matrix multiplication `multiply(A, B)`.
    - Both functions must perform calculations modulo `MOD`.
5. Compute `M_t = matrixPower(M, t)`.
6. Compute the final count vector `C_t = M_t * C_0`.
    - `C_t[i] = sum(M_t[i][j] * C_0[j] for j=0..25) % MOD`.
7. Sum all elements of `C_t` modulo `MOD` to get the final answer.

# Solutions
### Java

```java
class Solution {
private
  final int mod = (int)1 e9 + 7;
public
  int lengthAfterTransformations(String s, int t, List<Integer> nums) {
    final int m = 26;
    int[] cnt = new int[m];
    for (char c : s.toCharArray()) {
      cnt[c - 'a']++;
    }
    int[][] matrix = new int[m][m];
    for (int i = 0; i < m; i++) {
      int num = nums.get(i);
      for (int j = 1; j <= num; j++) {
        matrix[i][(i + j) % m] = 1;
      }
    }
    int[][] factor = matpow(matrix, t, m);
    int[] result = vectorMatrixMultiply(cnt, factor);
    int ans = 0;
    for (int val : result) {
      ans = (ans + val) % mod;
    }
    return ans;
  }
private
  int[][] matmul(int[][] a, int[][] b) {
    int n = a.length;
    int p = b.length;
    int q = b[0].length;
    int[][] res = new int[n][q];
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < p; k++) {
        if (a[i][k] == 0)
          continue;
        for (int j = 0; j < q; j++) {
          res[i][j] = (int)((res[i][j] + 1L * a[i][k] * b[k][j]) % mod);
        }
      }
    }
    return res;
  }
private
  int[][] matpow(int[][] mat, int power, int m) {
    int[][] res = new int[m][m];
    for (int i = 0; i < m; i++) {
      res[i][i] = 1;
    }
    while (power > 0) {
      if ((power & 1) != 0) {
        res = matmul(res, mat);
      }
      mat = matmul(mat, mat);
      power >>= 1;
    }
    return res;
  }
private
  int[] vectorMatrixMultiply(int[] vector, int[][] matrix) {
    int n = matrix.length;
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
      long sum = 0;
      for (int j = 0; j < n; j++) {
        sum = (sum + 1L * vector[j] * matrix[j][i]) % mod;
      }
      result[i] = (int)sum;
    }
    return result;
  }
}

```

### CPP

```cpp
class Solution { public: static constexpr int MOD = 1e9 + 7 ; static constexpr int M = 26 ; using Matrix = vector < vector < int >> ; Matrix matmul ( const Matrix & a , const Matrix & b ) { int n = a . size (), p = b . size (), q = b [ 0 ]. size (); Matrix res ( n , vector < int > ( q , 0 )); for ( int i = 0 ; i < n ; ++ i ) { for ( int k = 0 ; k < p ; ++ k ) { if ( a [ i ][ k ]) { for ( int j = 0 ; j < q ; ++ j ) { res [ i ][ j ] = ( res [ i ][ j ] + 1LL * a [ i ][ k ] * b [ k ][ j ] % MOD ) % MOD ; } } } } return res ; } Matrix matpow ( Matrix mat , int power ) { Matrix res ( M , vector < int > ( M , 0 )); for ( int i = 0 ; i < M ; ++ i ) res [ i ][ i ] = 1 ; while ( power ) { if ( power % 2 ) res = matmul ( res , mat ); mat = matmul ( mat , mat ); power /= 2 ; } return res ; } int lengthAfterTransformations ( string s , int t , vector < int >& nums ) { vector < int > cnt ( M , 0 ); for ( char c : s ) { cnt [ c - 'a' ] ++ ; } Matrix matrix ( M , vector < int > ( M , 0 )); for ( int i = 0 ; i < M ; ++ i ) { for ( int j = 1 ; j <= nums [ i ]; ++ j ) { matrix [ i ][( i + j ) % M ] = 1 ; } } Matrix cntMat ( 1 , vector < int > ( M )); for ( int i = 0 ; i < M ; ++ i ) cntMat [ 0 ][ i ] = cnt [ i ]; Matrix factor = matpow ( matrix , t ); Matrix result = matmul ( cntMat , factor ); int ans = 0 ; for ( int x : result [ 0 ]) { ans = ( ans + x ) % MOD ; } return ans ; } };
```

### Python

```python
class Solution : def lengthAfterTransformations ( self , s : str , t : int , nums : List [ int ]) -> int : mod = 10 ** 9 + 7 m = 26 cnt = [ 0 ] * m for c in s : cnt [ ord ( c ) - ord ( "a" )] += 1 matrix = [[ 0 ] * m for _ in range ( m )] for i , x in enumerate ( nums ): for j in range ( 1 , x + 1 ): matrix [ i ][( i + j ) % m ] = 1 def matmul ( a : List [ List [ int ]], b : List [ List [ int ]]) -> List [ List [ int ]]: n , p , q = len ( a ), len ( b ), len ( b [ 0 ]) res = [[ 0 ] * q for _ in range ( n )] for i in range ( n ): for k in range ( p ): if a [ i ][ k ]: for j in range ( q ): res [ i ][ j ] = ( res [ i ][ j ] + a [ i ][ k ] * b [ k ][ j ]) % mod return res def matpow ( mat : List [ List [ int ]], power : int ) -> List [ List [ int ]]: res = [[ int ( i == j ) for j in range ( m )] for i in range ( m )] while power : if power % 2 : res = matmul ( res , mat ) mat = matmul ( mat , mat ) power //= 2 return res cnt = [ cnt ] factor = matpow ( matrix , t ) result = matmul ( cnt , factor )[ 0 ] ans = sum ( result ) % mod return ans
```