[Leetcode] 3337. Total Characters in String After Transformations II

https://leetcode.com/problems/total-characters-in-string-after-transformations-ii/solutions/5972988/python-fast-pow-o-log-t/

initial

this is on a different level than the medium LC question.

We first have to understand Matrix.

So to simulate t number of simulations, we can use a 26x26 transformation matrix. matrix[i][j] =1 means that character i can be transformed to j.

The transformation rules are encoded in the matrix M, and raising it to the power of t gives the cumulative effect of t transformations

by multiplying with the charCount with this m^T, we can get the character counts after t transformations. This will be in a 1x26 matrix so we just add them up.

implementing this

So we have to create identity matrtix for power(). This is cuz when we multiply the matrixes there needs to be a 1 in the matrix to get useful value.

cuz rmb for normal calc we do

result = 1
while n > 0:
    if n is odd:
        result = result * x
    x = x * x
    n = n // 2
return result

where result =1? Same logic here we need that 1

also Remember that new_m[j][i] (or Mt[j][i]) represents the number of times a character that started at index j will contribute to the count of the character at index i after exactly t transformations.

sol

class Solution {
    private static final long MOD = 1_000_000_007;;
    public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
        long[][] m = new long[26][26];
        for(int i =0; i<26;i++) {
            int k = nums.get(i);
            for(int j=i+1; j<=i+k; j++){
                m[i][j%26]=1;
            }
        }
        long[][] new_m = power(m,t);
        long[] charCount = new long[26];
        for(char c:s.toCharArray()){
            charCount[c-'a']+=1;
        }
        long[] finalCount = new long[26];
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                finalCount[i]= (finalCount[i]+ (new_m[j][i] * charCount[j]) % MOD)%MOD;
            }
        }
        long ans =0;
        for(long count: finalCount){
            ans= (ans + count)%MOD;
        }
        return (int) ans;
    }

    public static long[][] power(long[][] matrix, int t) {
        int size = matrix.length;
        long[][] result = new long[size][size];
        for (int i = 0; i < size; i++) {
            result[i][i] = 1;
        }
        while(t>0){
            if((t&1)==1) {
                result = multiply(matrix,result);
            }
            matrix=multiply(matrix,matrix);
            t>>=1;
        }
        return result;
    }

    public static long[][] multiply(long[][] matrix1, long[][] matrix2){
        int row1 = matrix1.length;
        int row2 = matrix2.length;
        int col1= matrix1[0].length;
        int col2= matrix2[0].length;

        long[][] res = new long[row1][col2];
        for(int i=0; i<row1;i++){
            for(int j=0;j<col2;j++){
                for(int k=0;k<col1;k++){
                    res[i][j]= (res[i][j] + (matrix1[i][k]*matrix2[k][j]) %  MOD) %MOD;
                }
            }
        }
        return res;
    }
}

complexity

the power function is log t (cuz we are using bits)
the multiply function is t
so it is log t + t time

1 space