Total characters in string after transformations ii

Hash Table Math String Dynamic Programming Counting

58.1% acceptance

Feb 23, 2026

385

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.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn length_after_transformations(s: String, t: i32, nums: Vec<i32>) -> i32 {
    const MOD: u64 = 1_000_000_007;
    // Matrix exponentiation: 26x26 transition matrix
    // cnt[i] after one step = sum of cnt[j] for all j where i is in the range j+1..=j+nums[j] (mod 26)
    // Transition: T[i][j] = 1 if char j produces char i (i.e., (j+1)%(26) <= i <= (j+nums[j])%(26) wrapping)
    
    // Build transition matrix T: T[next_char][cur_char] = 1 if cur_char -> includes next_char
    let mut trans = [[0u64; 26]; 26];
    for j in 0..26 {
      let n = nums[j] as usize;
      for k in 1..=n {
        let next = (j + k) % 26;
        trans[next][j] = 1;
      }
    }
    
    // Matrix multiply
    let mat_mul = |a: &[[u64; 26]; 26], b: &[[u64; 26]; 26]| -> [[u64; 26]; 26] {
      let mut c = [[0u64; 26]; 26];
      for i in 0..26 {
        for k in 0..26 {
          if a[i][k] == 0 { continue; }
          for j in 0..26 {
            c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
          }
        }
      }
      c
    };
    
    // Matrix exponentiation
    let mut result = [[0u64; 26]; 26];
    for i in 0..26 { result[i][i] = 1; } // identity
    let mut base = trans;
    let mut exp = t as u64;
    while exp > 0 {
      if exp & 1 == 1 { result = mat_mul(&result, &base); }
      base = mat_mul(&base, &base);
      exp >>= 1;
    }
    
    // Initial count vector
    let mut cnt = [0u64; 26];
    for b in s.bytes() { cnt[(b - b'a') as usize] += 1; }
    
    // Apply result matrix to cnt
    let mut ans = 0u64;
    for i in 0..26 {
      let mut sum = 0u64;
      for j in 0..26 {
        sum = (sum + result[i][j] * cnt[j]) % MOD;
      }
      ans = (ans + sum) % MOD;
    }
    ans as i32
  }
}