Total Characters in String After Transformations II

Leetcode Problem:

• Total Characters in String After Transformations II

Summary

• Find the length of the resulting string after exactly t transformations on a given string s with a specific transformation rule and a given array of shifts.

Approach

• The solution uses a matrix representation of the transformation rule and exponentiates this matrix to the power of t
• It then multiplies the frequency of each character in the string by the corresponding row of the transformed matrix to get the new frequency of each character
• The sum of these frequencies gives the total length of the resulting string.

Complexity

• O(26^2 * t * log(t))

Explanation

• The solution first constructs a matrix representation of the transformation rule, where each entry at row i and column j represents the number of times the character corresponding to i is shifted by j positions
• This matrix is then exponentiated to the power of t using the powerMatrix function
• The frequency of each character in the string is then multiplied by the corresponding row of the transformed matrix to get the new frequency of each character
• The sum of these frequencies gives the total length of the resulting string.

Solution Code:

using ll = long long;

class Solution {
public:
    const int mod = 1e9 + 7;

    vector> multiplyMatrices(const vector> &A, const vector> &B) {
        int rowsA = A.size(), colsA = A[0].size(), colsB = B[0].size();
        vector> temp(rowsA, vector<__int128_t>(colsB, 0));
        vector> result(rowsA, vector(colsB, 0));

        for (int i = 0; i < rowsA; i++) {
            for (int j = 0; j < colsB; j++) {
                for (int k = 0; k < colsA; k++) {
                    temp[i][j] += A[i][k] * B[k][j];
                }
                result[i][j] = temp[i][j] % mod;
            }
        }
        return result;
    }

    vector> powerMatrix(vector> matrix, ll exponent) {
        vector> result(matrix.size(), vector(matrix.size(), 0));

        for (int i = 0; i < matrix.size(); i++) result[i][i] = 1;

        while (exponent > 0) {
            if (exponent % 2 == 1) result = multiplyMatrices(result, matrix);
            matrix = multiplyMatrices(matrix, matrix);
            exponent /= 2;
        }
        return result;
    }

    int lengthAfterTransformations(string s, int t, vector& nums) {
        vector> transform(26, vector(26, 0));

        for (int i = 0; i < 26; i++) {
            for (int shift = 0; shift < nums[i]; shift++) {
                transform[i][(i + 1 + shift) % 26]++;
            }
        }

        transform = powerMatrix(transform, t);
        vector> freq(1, vector(26, 0));
        for (char ch : s) {
            freq[0][ch - 'a']++;
        }

        freq = multiplyMatrices(freq, transform);
        int totalLength = 0;
        for (int count : freq[0]) {
            totalLength += count;
            if (totalLength >= mod) totalLength -= mod;
        }

        return totalLength;
    }
};