Scale Engineer

Total Characters in String After Transformations II

Hard
#2964Time: O(t * L_avg * max(nums)), where `L_avg` is the average length of the string across transformations. Since the length can grow exponentially, this is infeasible.Space: O(L_max), where `L_max` is the maximum length of the string, which can be huge.
Patterns
MathDynamic ProgrammingCounting
Data structures
Hash TableString

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the transformation process as described in the problem. It starts with the initial string s and, for t times, generates a new string by replacing each character of the current string with its corresponding transformation.

Algorithm

  1. Initialize currentString = s.
  2. Loop t times (from 1 to t): a. Create an empty StringBuilder called nextString. b. For each character c in currentString: i. Get the transformation length k = nums[c - 'a']. ii. For j from 1 to k: - Calculate the next character: nextChar = 'a' + ((c - 'a' + j) % 26). - Append nextChar to nextString. c. Update currentString = nextString.toString().
  3. Return currentString.length().

Walkthrough

The algorithm iterates t times. In each iteration, it constructs a new string. It traverses the current string character by character. For each character c, it determines the sequence of new characters based on nums[c - 'a']. The new characters are (c+1)%26, (c+2)%26, etc., wrapping around the alphabet from 'z' to 'a'. These new characters are appended to a temporary string builder. After iterating through all characters of the current string, the temporary string builder's content becomes the new current string for the next iteration. This process is repeated t times. Finally, the length of the resulting string is returned. Due to the potentially massive growth in string length and the large value of t, this approach is extremely slow and memory-intensive. It's not feasible for the given constraints and will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) errors.

// This is a conceptual implementation and will not pass due to performance issues.public int totalCharacters(String s, int t, int[] nums) {    String currentString = s;    for (int i = 0; i < t; i++) {        StringBuilder nextString = new StringBuilder();        for (char c : currentString.toCharArray()) {            int len = nums[c - 'a'];            for (int j = 1; j <= len; j++) {                char nextChar = (char) ('a' + (c - 'a' + j) % 26);                nextString.append(nextChar);            }        }        currentString = nextString.toString();        // The length can exceed memory limits long before t iterations.    }    return currentString.length(); // Modulo arithmetic is omitted for clarity of the basic idea.}

Complexity

Time

O(t * L_avg * max(nums)), where `L_avg` is the average length of the string across transformations. Since the length can grow exponentially, this is infeasible.

Space

O(L_max), where `L_max` is the maximum length of the string, which can be huge.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem description.

Cons

  • Extremely inefficient for large t as it requires t iterations.

  • The string length can grow exponentially, leading to Memory Limit Exceeded.

  • String concatenations in a loop are slow, leading to Time Limit Exceeded.

Solutions

class Solution {private  final int mod = (int)1 e9 + 7;public  int lengthAfterTransformations(String s, int t, List<Integer> nums) {    final int m = 26;    int[] cnt = new int[m];    for (char c : s.toCharArray()) {      cnt[c - 'a']++;    }    int[][] matrix = new int[m][m];    for (int i = 0; i < m; i++) {      int num = nums.get(i);      for (int j = 1; j <= num; j++) {        matrix[i][(i + j) % m] = 1;      }    }    int[][] factor = matpow(matrix, t, m);    int[] result = vectorMatrixMultiply(cnt, factor);    int ans = 0;    for (int val : result) {      ans = (ans + val) % mod;    }    return ans;  }private  int[][] matmul(int[][] a, int[][] b) {    int n = a.length;    int p = b.length;    int q = b[0].length;    int[][] res = new int[n][q];    for (int i = 0; i < n; i++) {      for (int k = 0; k < p; k++) {        if (a[i][k] == 0)          continue;        for (int j = 0; j < q; j++) {          res[i][j] = (int)((res[i][j] + 1L * a[i][k] * b[k][j]) % mod);        }      }    }    return res;  }private  int[][] matpow(int[][] mat, int power, int m) {    int[][] res = new int[m][m];    for (int i = 0; i < m; i++) {      res[i][i] = 1;    }    while (power > 0) {      if ((power & 1) != 0) {        res = matmul(res, mat);      }      mat = matmul(mat, mat);      power >>= 1;    }    return res;  }private  int[] vectorMatrixMultiply(int[] vector, int[][] matrix) {    int n = matrix.length;    int[] result = new int[n];    for (int i = 0; i < n; i++) {      long sum = 0;      for (int j = 0; j < n; j++) {        sum = (sum + 1L * vector[j] * matrix[j][i]) % mod;      }      result[i] = (int)sum;    }    return result;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem