3337. Total Characters in String After Transformations II

Description

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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n+26²+26³logt -> n+logt)
• Space complexity: O(26²+26 -> 1)

 

JavaScript

/**
 * @param {string} s
 * @param {number} t
 * @param {number[]} nums
 * @return {number}
 */
const lengthAfterTransformations = function (s, t, nums) {
  const MODULO = BigInt(10 ** 9 + 7);
  const BASE_CODE = 'a'.charCodeAt(0);
  const transformations = Array.from({ length: 26 }, () => new Array(26).fill(0n));

  for (let letter = 0; letter < 26; letter++) {
    for (let step = 1; step <= nums[letter]; step++) {
      const transform = (letter + step) % 26;

      transformations[letter][transform] += 1n;
    }
  }

  const matrixMult = (matrixA, matrixB) => {
    const n = matrixA.length;
    const result = new Array(26)
      .fill('')
      .map(_ => new Array(26).fill(0n));

    for (let a = 0; a < n; a++) {
      for (let b = 0; b < n; b++) {
        for (let k = 0; k < n; k++) {
          const multiple = matrixA[a][k] * matrixB[k][b];

          result[a][b] = (result[a][b] + multiple) % MODULO;
        }
      }
    }

    return result;
  };

  const matrixPow = (matrix, power) => {
    if (!power) {
      const n = matrix.length;
      const result = new Array(n)
        .fill('')
        .map(_ => new Array(n).fill(0n));

      for (let index = 0; index < n; index++) {
        result[index][index] = 1n;
      }

      return result;
    }

    if (power % 2) {
      return matrixMult(matrix, matrixPow(matrix, power - 1));
    }
    const halfMatrix = matrixPow(matrix, power / 2);

    return matrixMult(halfMatrix, halfMatrix);
  };

  const poweredTransformations = matrixPow(transformations, t);
  const counts = Array.from({ length: 26 }, () => 0n);
  const lengths = Array.from({ length: 26 }, () => 0n);

  for (const letter of s) {
    const code = letter.charCodeAt(0) - BASE_CODE;

    counts[code] += 1n;
  }

  for (let a = 0; a < 26; a++) {
    for (let b = 0; b < 26; b++) {
      lengths[a] = (lengths[a] + counts[a] * poweredTransformations[a][b]) % MODULO;
    }
  }

  return Number(lengths.reduce((result, length) => (result + length) % MODULO));
};