Total Characters in String After Transformations II
Source: leetcode
Difficulty: Hard
Tags: hash-table, math, string, dynamic-programming, counting

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** `109 + 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 <= s.length <= 105`
- `s` consists only of lowercase English letters.
- `1 <= t <= 109`
- `nums.length == 26`
- `1 <= nums[i] <= 25`




C++ solution:
class Solution {
public:
    using Matrix = vector<vector<long long>>;
    const int MOD = 1e9 + 7;
    Matrix multiply(const Matrix& A, const Matrix& B) {
        Matrix result(26, vector<long long>(26, 0));
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                for (int k = 0; k < 26; ++k) {
                    result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return result;
    }
    Matrix matrixExpo(Matrix base, int exp) {
        Matrix result(26, vector<long long>(26, 0));
        for (int i = 0; i < 26; ++i) {
            result[i][i] = 1;
        }
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = multiply(result, base);
            }
            base = multiply(base, base);
            exp /= 2;
        }
        return result;
    }
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        vector<long long> mp(26, 0);
        for (char c : s) {
            mp[c - 'a']++;
        }
        Matrix transform(26, vector<long long>(26, 0));
        for (int i = 0; i < 26; ++i) {
            for (int j = 1; j <= nums[i]; ++j) {
                transform[(i + j) % 26][i]++;
            }
        }
        Matrix poweredTransform = matrixExpo(transform, t);
        vector<long long> ans(26, 0);
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                ans[i] = (ans[i] + poweredTransform[i][j] * mp[j]) % MOD;
            }
        }
        long long sum = 0;
        for (int i = 0; i < 26; ++i) {
            sum = (sum + ans[i]) % MOD;
        }
        return static_cast<int>(sum);
    }
};

Go solution:
func lengthAfterTransformations(s string, t int, nums []int) int {
	const mod = 1000000007
	var M [26][26]int
	for i := 0; i < 26; i++ {
		steps := nums[i]
		for j := 1; j <= steps; j++ {
			idx := (i + j) % 26
			M[i][idx] = 1
		}
	}
	res := matPow(M, t, mod)
	ans := 0
	for i := 0; i < len(s); i++ {
		letter := int(s[i] - 'a')
		rowSum := 0
		for j := 0; j < 26; j++ {
			rowSum = (rowSum + res[letter][j]) % mod
		}
		ans = (ans + rowSum) % mod
	}
	return ans
}

func matMul(a, b [26][26]int, mod int) [26][26]int {
	var c [26][26]int
	for i := 0; i < 26; i++ {
		for k := 0; k < 26; k++ {
			if a[i][k] != 0 {
				for j := 0; j < 26; j++ {
					c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % mod
				}
			}
		}
	}
	return c
}

func matPow(matrix [26][26]int, exp, mod int) [26][26]int {
	var res [26][26]int
	for i := 0; i < 26; i++ {
		res[i][i] = 1
	}
	for exp > 0 {
		if exp&1 == 1 {
			res = matMul(res, matrix, mod)
		}
		matrix = matMul(matrix, matrix, mod)
		exp /= 2
	}
	return res
}

Java solution:
class Solution {
    private final int mod = (int) (1e9 + 7);
    public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
        if(t == 0) return s.length() % mod;
        long[] freq = new long[26];
        for(char ch : s.toCharArray()) {
            freq[ch - 'a']++;
        }
        long[][] m = new long[26][26];
        for(int i=0; i<26; i++) {
            int num = nums.get(i);
            for(int j=1; j<=num; j++) {
                m[i][(i + j) % 26] = 1;
            }
        }
        long[][] mt = matrixPower(m, t);
        long[] rowsum = new long[26];
        for(int i=0; i<26; i++) {
            for(int j=0; j<26; j++) {
                rowsum[i] = (rowsum[i] + mt[i][j]) % mod;
            }
        }
        long total = 0;
        for(int i=0; i<26; i++) {
            total = (total + (freq[i]*rowsum[i]) % mod) % mod;
        }
        return (int) total;
    }
    private long[][] matrixPower(long[][] m, int power) {
        long[][] ans = new long[26][26];
        for(int i=0; i<26; i++) {
            ans[i][i] = 1;
        }
        long[][] base = new long[26][26];
        for(int i=0; i<26; i++) {
            System.arraycopy(m[i], 0, base[i], 0, 26);
        }
        while(power > 0) {
            if((power & 1) == 1) ans = multiply(ans, base);
            base = multiply(base, base);
            power >>= 1;
        }
        return ans;
    }
    private long[][] multiply(long[][] a, long[][] b) {
        long[][] c = new long[26][26];
        for(int i=0; i<26; i++) {
            for(int k=0; k<26; k++) {
                if(a[i][k] != 0) {
                    for(int j=0; j<26; j++) {
                        c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % mod;
                    }
                }
            }
        }
        return c;
    }
}

JavaScript solution:
const MOD = 1e9 + 7;
const MODn = BigInt(MOD);

var lengthAfterTransformations = function(s, t, nums) {
    let vec = new Array(26).fill(0);
    for(let i = 0; i < s.length; ++i) {
        let chr = s.charCodeAt(i) - 'a'.charCodeAt(0);
        vec[chr] += 1;
    }
    let mat = new Array(26).fill(0).map(_ => new Array(26).fill(0n));
    for(let i = 0; i < 26; ++i) {
        let count = nums[i];
        let j = (i + 1) % 26;
        while(count > 0) {
            mat[i][j] = 1n;
            --count;
            
            j = (j + 1) % 26;
        }

    }

    mat = matPow(mat, t);
    let result = 0;
    for(let i = 0; i < 26; ++i) {
        for(let j = 0; j < 26; ++j) {
            result += vec[i] * Number(mat[i][j]);
        }
        result = result % MOD;
    }

    return result;
}

function multiplyInto(mat1, mat2, output, tmp) {

    for(let i = 0; i < output.length; ++i) {
        for(let j = 0; j < output[0].length; ++j) {
            let result = 0n;
            for(let k = 0; k < output.length; ++k) {
                result += mat1[i][k] * mat2[k][j];
                result %= MODn;
            }
            tmp[i][j] = result;
        }
    }

    for(let i = 0; i < output.length; ++i) {
        for(let j = 0; j < output[0].length; ++j) {
            output[i][j] = tmp[i][j];
        }
    }
}

function matPow(mat, exp) {
    const result = new Array(mat.length).fill(0).map(_ => mat[0].slice(0).fill(0n));
    const tmp = new Array(mat.length).fill(0).map(_ => mat[0].slice(0));
    for(let i = 0; i < result.length; ++i) {
        result[i][i] = 1n;
    }

    while (exp) {
        if (exp & 1) { multiplyInto(mat, result, result, tmp); }
        multiplyInto(mat, mat, mat, tmp);
        exp >>>= 1;
    }

    return result;
}

Python solution:
def mat_mul(mat1, mat2, mod):
    res = [[0] * len(mat2[0]) for _ in range(len(mat1))]
    for i in range(len(mat1)):
        for j in range(len(mat2[0])):
            for k in range(len(mat2)):
                res[i][j] += mat1[i][k] * mat2[k][j]
            res[i][j] %= mod
    return res

def mat_pow(mat, n, mod):
    size = len(mat)
    res = [[1 if i == j else 0 for j in range(size)] for i in range(size)]
    while n > 0:
        if n & 1:
            res = mat_mul(res, mat, mod)
        mat = mat_mul(mat, mat, mod)
        n >>= 1
    return res

class Solution:
    def lengthAfterTransformations(self, s: str, t: int, A: List[int]) -> int:
        M = [[0] * 26 for i in range(26)]
        for i,k in enumerate(A):
            for j in range(i + 1, i + k + 1):
                M[i][j % 26] = 1
        mod = 10 ** 9 + 7
        Mt = mat_pow(M, t, mod)
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        res = mat_mul([count], Mt, mod)
        return sum(res[0]) % mod

Ruby solution:
def length_after_transformations(s, t, nums)
  mod = 1000000007
  freq = Array.new(26, 0)
  s.each_char { |c| freq[c.ord - 97] += 1 }
  transform = Array.new(26) { Array.new(26, 0) }
  26.times do |j|
    (1..nums[j]).each { |step| transform[(j + step) % 26][j] = 1 }
  end
  multiply = ->(a, b) {
    c = Array.new(26) { Array.new(26, 0) }
    26.times do |i|
      26.times do |k|
        ak = a[i][k]
        next if ak == 0
        26.times do |j|
          c[i][j] = (c[i][j] + ak * b[k][j]) % mod
        end
      end
    end
    c
  }
  matrixExpo = ->(base, exp) {
    result = Array.new(26) { Array.new(26, 0) }
    26.times { |i| result[i][i] = 1 }
    while exp > 0
      result = multiply.call(result, base) if exp.odd?
      base = multiply.call(base, base)
      exp /= 2
    end
    result
  }
  powered_transform = matrixExpo.call(transform, t)
  new_freq = Array.new(26, 0)
  26.times do |i|
    26.times do |j|
      new_freq[i] = (new_freq[i] + powered_transform[i][j] * freq[j]) % mod
    end
  end
  new_freq.sum % mod
end