3337: Total-Characters-in-String-After-Transformations-II
Hard

Main Algorithm:

Looking at this question, since there is no difference between applying t transformations on separate letters of the same type, it makes intuitive sense to precompute the number of letters you are left after transforming each letter in the alphabet t times.

But how would you do this?

You can do this by rephrasing the question problem. For example, given the nums array:

$$nums = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26],$$

we can compute a 26 x 26 matrix to compute the letters formed after 1 transformation.

In this 26 x 26 matrix, each row corresponds to the letters formed after 1 transformation. For example, given the nums array above, if we take the letter c located at index position 2jI, since nums[2] = 3, it means the 3 letters after c will be formed. In the matrix, that specific row (row 3) will look like:

$$matrix[row 3] = [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]$$

If we do this for all the 26 rows, then we will end up with a transformation matrix, A. This transformation matrix basically means that, if we want to find the frequency of any letter, we can just check the index, we can initialize a vector, v, of height 26, with the value at each index being 1,

$$v = [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]^T$$

and then do the operation A * v so that each index is thus the length of each letter after 1 transformation.

For consequent transformations, we can just continue multiplying v by A. This leads us to our first (and only) optimisation (there is too many…)

Square and Multiply Algorithm:

To slightly speed-up the multiplication process, realise that we can convert it to O(log(t)).

Given t = 23, we can convert t into binary to get 0b10111.

Since multiplying v by A 23 times is just A^23 * v Now, using the binary representation of 23, we get A^23 = A^1 + A^2 + A^4 + A^16.

Overall, that means instead of doing ... * (A * (A * v)) 23 times (which is equivalent to A^23 * v) we can just continuously square A, and break down the original equation into

A^23 * v = (A^1 * v) + (A^2 * v) + (A^4 * v) + (A^16 * v).

code

class Solution {
public:
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        vector<vector<long>> matrix (26, vector<long>(26, 0));
        vector<vector<long>> v (26, vector<long>(1, 1));

        for (int i = 0; i < nums.size(); ++i) {
            for (int j = 1; j <= nums[i]; ++j) {
                ++matrix[i][(i+j)%26];
            }
        }

        int n = t;
        while (n > 0) {
            if (n%2 == 1) {
                v = matrixMultiplication(matrix, v);
            }

            matrix = matrixMultiplication(matrix, matrix);
            n >>= 1;
        }

        long ans = 0;
        for (char& c : s) {
            ans = (ans + v[c-'a'][0]) % MOD;
        }
        return ans;
    }
private:
    static const int MOD = 1e9+7;
    vector<vector<long>> matrixMultiplication(vector<vector<long>> &leftMatrix, vector<vector<long>> &rightMatrix) {
        vector<vector<long>> result (leftMatrix.size(), vector<long>(rightMatrix[0].size(), 0));

        for (int i = 0; i < leftMatrix.size(); ++i) {
            for (int j = 0; j < rightMatrix[0].size(); ++j) {
                for (int k = 0; k < rightMatrix.size(); ++k) {
                    result[i][j] = (result[i][j] + leftMatrix[i][k] * rightMatrix[k][j]) % MOD;
                }
            }
        }

        return result;
    }
};

complexity

learnings