Total Characters in String After Transformations II

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

Examples

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 <= 10^5
• s consists only of lowercase English letters.
• 1 <= t <= 10^9
• nums.length == 26
• 1 <= nums[i] <= 25

Solution

Method 1 - Using Matrix Exponentiation

The problem revolves around efficiently simulating a series of transformations on the occurrences of characters in the string s. The naive approach of iterating through each transformation step is too slow, especially for large values of t. Instead, we leverage the mathematical concept of matrix exponentiation to perform the transformations efficiently.

Note that:

1. Character Transformations: For each transformation:
   • A character c transforms into several other characters based on nums[c].
   • The transformations wrap around the 26 letters of the alphabet.
2. Matrix Representation:
   • We represent transformations using a transition matrix T, where T[i][j] = 1 if character j can transform into character i, and T[i][j] = 0 otherwise.
   • The recurrence relation can be expressed as: $f(i) = T \times f(i-1)$, 1. - where f(i) is the column vector representing character frequencies at the i-th step.
3. Efficiency with Matrix Exponentiation:
   • Direct computation across t transformations is inefficient. Instead, we compute ( T^t ), the t-th matrix power, using matrix exponentiation by squaring.
   • This reduces the time complexity from ( O(t \times n^3) ) to ( O(\log(t) \times n^3) ), where ( n = 26 ) (number of characters).

Approach

1. Matrix Construction:

   • Build the transformation matrix T based on nums. If character j transforms to character i, set T[i][j] = 1.

2. Matrix Exponentiation:

   • Calculate T^t using exponentiation by squaring.

3. Initial Frequency Vector:

   • Construct the frequency vector ( f(0) ), where f(0)[i] is the number of occurrences of character i in the input string s.

4. Final Frequency Vector:

   • Multiply the matrix T^t with f(0) to compute f(t), which represents the frequencies of all characters after t transformations.

5. Result Calculation:

   • Sum the values in f(t) to obtain the total length of the transformed string.

Code

Java

class Solution {

    private static final int MOD = (int) 1e9 + 7;
    private static final int ALPHABET_SIZE = 26;

    private static class Matrix {

        int[][] values = new int[ALPHABET_SIZE][ALPHABET_SIZE];

        Matrix() {}

        Matrix multiply(Matrix other) {
            Matrix result = new Matrix();
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                for (int j = 0; j < ALPHABET_SIZE; j++) {
                    for (int k = 0; k < ALPHABET_SIZE; k++) {
                        result.values[i][j] = (int) ((result.values[i][j] +
                                (long) this.values[i][k] * other.values[k][j]) % MOD);
                    }
                }
            }
            return result;
        }

        static Matrix identity() {
            Matrix identityMatrix = new Matrix();
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                identityMatrix.values[i][i] = 1;
            }
            return identityMatrix;
        }

        Matrix exponentiate(int power) {
            Matrix result = identity();
            Matrix base = this;
            while (power > 0) {
                if ((power & 1) == 1) {
                    result = result.multiply(base);
                }
                base = base.multiply(base);
                power >>= 1;
            }
            return result;
        }
    }

    public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
        // Build transformation matrix
        Matrix transformationMatrix = new Matrix();
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            for (int j = 1; j <= nums.get(i); j++) {
                transformationMatrix.values[(i + j) % ALPHABET_SIZE][i] = 1;
            }
        }

        // Compute transformationMatrix raised to the power of t
        Matrix finalMatrix = transformationMatrix.exponentiate(t);

        // Build the initial frequency vector
        int[] frequencyVector = new int[ALPHABET_SIZE];
        for (char ch : s.toCharArray()) {
            frequencyVector[ch - 'a']++;
        }

        // Compute the result using the finalMatrix
        int resultLength = 0;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            for (int j = 0; j < ALPHABET_SIZE; j++) {
                resultLength = (int) ((resultLength +
                        (long) finalMatrix.values[i][j] * frequencyVector[j]) % MOD);
            }
        }

        return resultLength;
    }
}

Python

MOD = int(1e9 + 7)
L = 26

class Solution:
    class Mat:
        def __init__(self):
            self.a = [[0] * L for _ in range(L)]

        def mul(self, other):
            result = Solution.Mat()
            for i in range(L):
                for j in range(L):
                    for k in range(L):
                        result.a[i][j] = (result.a[i][j] +
                                        self.a[i][k] * other.a[k][j]) % MOD
            return result
        
        @staticmethod
        def identity():
            m = Solution.Mat()
            for i in range(L):
                m.a[i][i] = 1
            return m
        
        def quickmul(self, power):
            result = Solution.Mat.identity()
            base = self
            while power > 0:
                if power % 2 == 1:
                    result = result.mul(base)
                base = base.mul(base)
                power //= 2
            return result

    def length_after_transformations(self, s: str, t: int, nums: list[int]) -> int:
        T = Solution.Mat()
        for i in range(L):
            for j in range(1, nums[i] + 1):
                T.a[(i + j) % L][i] = 1

        T_t = T.quickmul(t)
        f = [0] * L
        for ch in s:
            f[ord(ch) - ord('a')] += 1

        ans = 0
        for i in range(L):
            for j in range(L):
                ans = (ans + T_t.a[i][j] * f[j]) % MOD
        return ans

Complexity

• ⏰ Time complexity: O(log(t) * n^3)
  • Matrix Construction: O(n*n) where ( n = 26 )
  • Matrix Exponentiation: O(log(t) * n^3)
  • Matrix-Vector Multiplication: O(n^2)
• 🧺 Space complexity: O(n^2) for storing matrix and vectors.