Problem Informations

• Problem Index: 3337
• Problem Link: Total Characters in String After Transformations II
• Topics: Hash Table, Math, String, Dynamic Programming, Counting

Problem Description

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$.

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

Intuition

The problem requires transforming each character in a string s through a series of transformations defined by an integer array nums and an integer t, which dictates how many transformations to apply. Each transformation changes a character to a sequence of subsequent characters in the alphabet based on the nums array. The challenge lies in handling the potentially exponential growth of the string due to repeated transformations, especially given the constraints that allow a large number of transformations (t up to $10^9$).

The key to solving this problem is recognizing that the direct simulation of transformations up to t is infeasible due to both time and space constraints. Instead, this problem can be addressed through matrix exponentiation, which allows us to efficiently compute the result of multiple transformations compactly.

Approach

The approach utilizes linear algebra concepts, particularly focusing on matrix multiplication and exponentiation to efficiently compute the result of t transformations.

1. Initial State Representation:

   • Start by representing the string s as a frequency vector initialCount, which is a 26-dimensional vector (since there are 26 lowercase English letters). Each element at index i in the vector represents the count of the letter i + 'a' in s.

2. Transformation Matrix Construction:

   • Construct a 26x26 transformation matrix M where each row represents the result of transforming a particular character according to nums. Specifically, if character i is transformed based on nums[i], the matrix entry M[(i + j) % 26][i] is set to 1 for each j from 1 to nums[i]. This encapsulates wrapping around the alphabet.

3. Matrix Exponentiation:

   • Compute the matrix M raised to the power t, denoted as M^t. This operation, done efficiently using exponentiation by squaring, gives us the effect of performing t transformations in a compact form.

4. Final Transformation Application:

   • Multiply the matrix M^t by the initial frequency vector initialCount to get a new vector finalCount. Each entry in finalCount represents the count of each character after t transformations.

5. Calculate the Final Length:

   • Sum all elements in finalCount to determine the total length of the transformed string. Since the length may be large, take the result modulo $10^9 + 7$ to ensure it fits within the constraints.

This matrix exponentiation approach efficiently computes the effect of multiple transformations without explicitly expanding the string, which is crucial given the potential for exponential growth in string length.

Code

C++

#include <array>
#include <vector>
#include <string>
using namespace std;

class Solution {
    static constexpr long long MOD = 1'000'000'007;
    using Mat = array<array<long long, 26>, 26>; // Alias for a 26x26 matrix type
    using Vec = array<long long, 26>;            // Alias for a 26-element vector type

    /* -------- Matrix Operations -------- */

    // Matrix Multiplication: Multiplies two 26x26 matrices A and B
    static Mat mulMat(const Mat& A, const Mat& B) {
        Mat C{}; // Resulting matrix initialized to zero
        for (int i = 0; i < 26; ++i)
            for (int k = 0; k < 26; ++k)
                if (A[i][k]) {
                    long long aik = A[i][k];
                    for (int j = 0; j < 26; ++j) {
                        C[i][j] += aik * B[k][j] % MOD;
                        if (C[i][j] >= MOD)
                            C[i][j] -= MOD; // Ensure C[i][j] is within MOD
                    }
                }
        return C;
    }

    // Matrix-Vector Multiplication: Multiplies matrix A with vector v
    static Vec mulMatVec(const Mat& A, const Vec& v) {
        Vec res{}; // Resulting vector initialized to zero
        for (int i = 0; i < 26; ++i) {
            long long sum = 0;
            for (int j = 0; j < 26; ++j) {
                sum += A[i][j] * v[j] % MOD;
                if (sum >= MOD)
                    sum -= MOD; // Ensure sum is within MOD
            }
            res[i] = sum;
        }
        return res;
    }

    // Matrix Exponentiation: Computes base^exp using matrix exponentiation by squaring
    static Mat matPow(Mat base, int exp) {
        Mat ret{}; // Identity matrix initialization
        for (int i = 0; i < 26; ++i)
            ret[i][i] = 1;

        while (exp) {
            if (exp & 1)
                ret = mulMat(ret, base);
            base = mulMat(base, base);
            exp >>= 1;
        }
        return ret;
    }

public:
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        // 1. Convert the initial string into a 26-dimensional frequency vector
        Vec initialCount{};
        for (char c : s)
            initialCount[c - 'a']++;

        // 2. Build the 26x26 transformation matrix M for one transformation
        Mat M{}; // Initialize to zero
        for (int i = 0; i < 26; ++i)
            for (int j = 1; j <= nums[i]; j++)
                M[(i + j) % 26][i] = 1;

        // 3. Compute M^t (M raised to the power of t)
        Mat Mt = matPow(M, t);

        // 4. Multiply the resulting transformation matrix with the initial vector
        //    and sum up the elements to get the final length
        Vec finalCount = mulMatVec(Mt, initialCount);
        long long result = 0;
        for (long long x : finalCount) {
            result += x;
            if (result >= MOD)
                result -= MOD; // Ensure result is within MOD
        }
        return static_cast<int>(result);
    }
};

Python

from typing import List

class Solution:
    MOD = 1_000_000_007

    @staticmethod
    def mulMat(A, B):
        C = [[0] * 26 for _ in range(26)]  # Resulting matrix initialized to zero
        for i in range(26):
            for k in range(26):
                if A[i][k]:
                    aik = A[i][k]
                    for j in range(26):
                        C[i][j] += aik * B[k][j] % Solution.MOD
                        if C[i][j] >= Solution.MOD:
                            C[i][j] -= Solution.MOD  # Ensure C[i][j] is within MOD
        return C

    @staticmethod
    def mulMatVec(A, v):
        res = [0] * 26  # Resulting vector initialized to zero
        for i in range(26):
            sum = 0
            for j in range(26):
                sum += A[i][j] * v[j] % Solution.MOD
                if sum >= Solution.MOD:
                    sum -= Solution.MOD  # Ensure sum is within MOD
            res[i] = sum
        return res

    @staticmethod
    def matPow(base, exp):
        ret = [[0] * 26 for _ in range(26)]  # Identity matrix initialization
        for i in range(26):
            ret[i][i] = 1

        while exp:
            if exp & 1:
                ret = Solution.mulMat(ret, base)
            base = Solution.mulMat(base, base)
            exp >>= 1
        return ret

    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        # 1. Convert the initial string into a 26-dimensional frequency vector
        initialCount = [0] * 26
        for c in s:
            initialCount[ord(c) - ord('a')] += 1

        # 2. Build the 26x26 transformation matrix M for one transformation
        M = [[0] * 26 for _ in range(26)]  # Initialize to zero
        for i in range(26):
            for j in range(1, nums[i] + 1):
                M[(i + j) % 26][i] = 1

        # 3. Compute M^t (M raised to the power of t)
        Mt = self.matPow(M, t)

        # 4. Multiply the resulting transformation matrix with the initial vector
        #    and sum up the elements to get the final length
        finalCount = self.mulMatVec(Mt, initialCount)
        result = 0
        for x in finalCount:
            result += x
            if result >= self.MOD:
                result -= self.MOD  # Ensure result is within MOD
        return result

Complexity

• Time complexity: $O(26^3 \log t + n)$

  The time complexity can be broken down into distinct parts:

  1. Matrix Multiplication and Exponentiation: The matrix multiplications (both matrix-matrix and matrix-vector product) involve 26x26 matrices, leading to $O(26^3)$ operations per multiplication. Matrix exponentiation using exponentiation by squaring requires $\log t$ multiplications, resulting in $O(26^3 \log t)$ time complexity.
  2. Initial Vector Setup and Final Calculation: Creating the initial frequency vector requires traversing the string s, which takes $O(n)$. The final length is calculated by summing elements of the resulting vector, effectively another $O(26)$ operation, which is negligible compared to matrix operations.

  Thus, the overall time complexity is dominated by the matrix operations, i.e., $O(26^3 \log t + n)$.

• Space complexity: $O(26^2)$

  The space complexity is determined by storing the 26x26 transformation matrix and additional vectors used during calculations:

  1. Matrix Storage: The primary space is consumed by the 26x26 matrix, which is $O(26^2)$.
  2. Vector Storage: Frequency vectors are of size 26, i.e., $O(26)$, but they are significantly smaller than matrix storage.

  As the matrix’s space requirement dominates, the space complexity is $O(26^2)$.