Leetcode 3335. Total Characters in String After Transformations I

Jimmy   May 13, 2025   1582 words   ~40 mins
#Hash Table #Math #String #Dynamic Programming #Counting

Table of Contents

Problem Informations

Problem 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 $10^9 + 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 \leq s.\text{length} \leq 10^5$
  • s consists only of lowercase English letters.
  • $1 \leq t \leq 10^5$

Intuition

The problem revolves around performing a series of transformations on a string, with each character either being incremented to the next alphabetical character or replaced by a longer string in the case of ‘z’. The challenge lies in efficiently determining the length of the string after a potentially large number of transformations (up to $10^5$), as direct simulation would be computationally prohibitive due to the exponential growth of the string’s length.

The key observation that guides our approach is that for any character other than ‘z’, its transformation path is straightforward: it progresses from one character to the next. However, for ‘z’, it is replaced by two characters, ‘a’ and ‘b’, thereby causing an exponential increase in the total length. To efficiently compute the length after multiple transformations, we can leverage the properties of linear transformations and powers of matrices, which allow us to encode these character transformations in a matrix and compute their effect iteratively through matrix exponentiation.

Approach

To determine the length of the string after t transformations, we employ a matrix exponentiation strategy that represents character transformations as linear transformations in a 26-dimensional space (corresponding to the 26 alphabetic characters).

  1. Representation as Vectors and Matrices:

    • We represent the initial string s using a 26-dimensional vector characterCount, where each element corresponds to the count of a particular character (‘a’ to ‘z’).
    • Define a 26x26 transformation matrix M that encodes the rules of transformation:
      • For characters ‘a’ to ‘y’, each transitions to the next character, hence the matrix M will have M[i][i-1] = 1.
      • For ‘z’, it transitions to both ‘a’ and ‘b’, captured by setting M[0][25] = 1 and M[1][25] = 1.

  2. Matrix Exponentiation:

    • Compute the matrix power M^t using fast matrix exponentiation. This efficiently calculates the effect of applying the transformation matrix t times.
    • This approach leverages the properties of matrix multiplication to compute the result in logarithmic time relative to t.

  3. Transformation Application:

    • Multiply the initial characterCount vector by the matrix M^t, resulting in a new vector that represents the transformed character counts.
    • Sum the elements of this resulting vector to get the total length of the string after t transformations.

  4. Modulo Operation:

    • Since the potential length can be very large, all operations involving counts are performed modulo $10^9 + 7$ to prevent overflow and adhere to the problem constraints.

By utilizing matrix exponentiation, this approach efficiently computes the length of the string after a large number of transformations, within acceptable time complexity, specifically $O(T \log t)$, where $T$ is a constant due to the fixed alphabet size.

Code

C++

#include <array>
#include <string>

class Solution {
    // Define the large prime modulus
    static constexpr long long MOD = 1'000'000'007;
    // Define a matrix type with fixed dimensions 26x26
    using Mat = std::array<std::array<long long, 26>, 26>;
    // Define a vector type with fixed dimension 26
    using Vec = std::array<long long, 26>;

    // Multiply two matrices A and B
    static Mat multiplyMatrix(const Mat& A, const Mat& B) {
        Mat C{};
        for (int i = 0; i < 26; ++i) {
            for (int k = 0; k < 26; ++k) {
                if (A[i][k]) {
                    long long a_ik = A[i][k];
                    for (int j = 0; j < 26; ++j) {
                        C[i][j] += a_ik * B[k][j] % MOD;
                        if (C[i][j] >= MOD) C[i][j] -= MOD;
                    }
                }
            }
        }
        return C;
    }

    // Multiply a matrix A with a vector v
    static Vec multiplyMatrixVector(const Mat& A, const Vec& v) {
        Vec result{};
        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;
            }
            result[i] = sum;
        }
        return result;
    }

    // Compute the power of a matrix using fast exponentiation
    static Mat matrixPower(Mat base, int exp) {
        Mat result{}; // Initialize the identity matrix
        for (int i = 0; i < 26; ++i) result[i][i] = 1;

        while (exp) {
            if (exp & 1) result = multiplyMatrix(result, base);
            base = multiplyMatrix(base, base);
            exp >>= 1;
        }
        return result;
    }

public:
    // Calculate the length of the string after t transformations
    int lengthAfterTransformations(std::string s, int t) {
        // Step 1: Convert the initial string into a 26-dimensional count vector
        Vec characterCount{};
        for (char c : s) characterCount[c - 'a']++;

        // Step 2: Create a 26x26 transformation matrix M for one transformation
        Mat M{}; // Initially all elements are zero
        for (int i = 0; i < 25; ++i) // Transition from x to x+1
            M[i + 1][i] = 1;
        M[0][25] = 1; // Transition from 'z' to 'a'
        M[1][25] = 1; // Transition from 'z' to 'b'

        // Step 3: Compute the matrix M^t
        Mat Mt = matrixPower(M, t);

        // Step 4: Multiply the vector and matrix to get the final character counts
        Vec finalCount = multiplyMatrixVector(Mt, characterCount);
        long long finalLength = 0;
        for (long long count : finalCount) {
            finalLength += count;
            if (finalLength >= MOD) finalLength -= MOD;
        }
        return static_cast<int>(finalLength);
    }
};

Python

class Solution:
    # Define the large prime modulus
    MOD = 1_000_000_007
    # Define a matrix type with fixed dimensions 26x26
    Mat = list[list[int]]
    # Define a vector type with fixed dimension 26
    Vec = list[int]

    # Multiply two matrices A and B
    @staticmethod
    def multiplyMatrix(A: 'Solution.Mat', B: 'Solution.Mat') -> 'Solution.Mat':
        C = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for k in range(26):
                if A[i][k]:
                    a_ik = A[i][k]
                    for j in range(26):
                        C[i][j] += a_ik * B[k][j] % Solution.MOD
                        if C[i][j] >= Solution.MOD:
                            C[i][j] -= Solution.MOD
        return C

    # Multiply a matrix A with a vector v
    @staticmethod
    def multiplyMatrixVector(A: 'Solution.Mat', v: 'Solution.Vec') -> 'Solution.Vec':
        result = [0] * 26
        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
            result[i] = sum
        return result

    # Compute the power of a matrix using fast exponentiation
    @staticmethod
    def matrixPower(base: 'Solution.Mat', exp: int) -> 'Solution.Mat':
        result = [[0] * 26 for _ in range(26)]  # Initialize the identity matrix
        for i in range(26):
            result[i][i] = 1

        while exp:
            if exp & 1:
                result = Solution.multiplyMatrix(result, base)
            base = Solution.multiplyMatrix(base, base)
            exp >>= 1
        return result

    # Calculate the length of the string after t transformations
    def lengthAfterTransformations(self, s: str, t: int) -> int:
        # Step 1: Convert the initial string into a 26-dimensional count vector
        characterCount = [0] * 26
        for c in s:
            characterCount[ord(c) - ord('a')] += 1

        # Step 2: Create a 26x26 transformation matrix M for one transformation
        M = [[0] * 26 for _ in range(26)] # Initially all elements are zero
        for i in range(25): # Transition from x to x+1
            M[i + 1][i] = 1
        M[0][25] = 1 # Transition from 'z' to 'a'
        M[1][25] = 1 # Transition from 'z' to 'b'

        # Step 3: Compute the matrix M^t
        Mt = Solution.matrixPower(M, t)

        # Step 4: Multiply the vector and matrix to get the final character counts
        finalCount = Solution.multiplyMatrixVector(Mt, characterCount)
        finalLength = 0
        for count in finalCount:
            finalLength += count
            if finalLength >= Solution.MOD:
                finalLength -= Solution.MOD
        return finalLength

Complexity

  • Time complexity: $O(26^3 \cdot \log{t})$

    The time complexity is dominated by the matrix exponentiation process, which involves matrix multiplication. Since the size of the matrix is fixed at $26 \times 26$, matrix multiplication has a constant complexity of $O(26^3)$. The matrix exponentiation is performed using fast exponentiation (or exponentiation by squaring), which takes $O(\log{t})$ steps. Therefore, the total time complexity is $O(26^3 \cdot \log{t})$, which is effectively a constant-time operation due to the fixed dimension of the matrix.

  • Space complexity: $O(1)$

    The space complexity is $O(1)$ because the space used by the matrices and vectors does not increase with the input size or number of transformations, $t$. The matrix and vector dimensions are constant as they represent the fixed set of 26 alphabet characters, leading to constant space usage. Thus, the space complexity remains constant.

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.