3337. Total Characters in String After Transformations II LeetCode Solution
In this guide, you will get 3337. Total Characters in String After Transformations II LeetCode Solution with the best time and space complexity. The solution to Total Characters in String After Transformations II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Total Characters in String After Transformations II
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”
‘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
Complexity Analysis
Time Complexity: O(|\texttt{s}| + \log t)
Space Complexity: O(26^2 + 26) = O(1)
3337. Total Characters in String After Transformations II LeetCode Solution in C++
class Solution {
public:
// Similar to 3335. Total Characters in String After Transformations I
int lengthAfterTransformations(string s, int t, vector<int>& nums) {
// T[i][j] := the number of ways to transform ('a' + i) to ('a' + j)
const vector<vector<int>> T = getTransformationMatrix(nums);
const vector poweredT = matrixPow(T, t);
vector<int> count(26);
// lengths[i] := the total length of ('a' + i) after t transformations
vector<long> lengths(26);
for (const char c : s)
++count[c - 'a'];
for (int i = 0; i < 26; ++i)
for (int j = 0; j < 26; ++j) {
lengths[j] += static_cast<long>(count[i]) * poweredT[i][j];
lengths[j] %= kMod;
}
return accumulate(lengths.begin(), lengths.end(), 0L) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
vector<vector<int>> getTransformationMatrix(const vector<int>& nums) {
vector<vector<int>> T(26, vector<int>(26));
for (int i = 0; i < nums.size(); ++i)
for (int step = 1; step <= nums[i]; ++step)
++T[i][(i + step) % 26];
return T;
}
vector<vector<int>> getIdentityMatrix(int sz) {
vector<vector<int>> I(sz, vector<int>(sz));
for (int i = 0; i < sz; ++i)
I[i][i] = 1;
return I;
}
// Returns A * B.
vector<vector<int>> matrixMult(const vector<vector<int>>& A,
const vector<vector<int>>& B) {
const int sz = A.size();
vector<vector<int>> C(sz, vector<int>(sz));
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j)
for (int k = 0; k < sz; ++k)
C[i][j] = (C[i][j] + static_cast<long>(A[i][k]) * B[k][j]) % kMod;
return C;
}
// Returns M^n.
vector<vector<int>> matrixPow(const vector<vector<int>>& M, int n) {
if (n == 0)
return getIdentityMatrix(M.size());
if (n % 2 == 1)
return matrixMult(M, matrixPow(M, n - 1));
return matrixPow(matrixMult(M, M), n / 2);
}
}; /* code provided by PROGIEZ */
3337. Total Characters in String After Transformations II LeetCode Solution in Java
class Solution {
// Similar to 3335. Total Characters in String After Transformations I
public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
// T[i][j] := the number of ways to transform ('a' + i) to ('a' + j)
int[][] T = getTransformationMatrix(nums);
int[][] poweredT = matrixPow(T, t);
int[] count = new int[26];
// lengths[i] := the total length of ('a' + i) after t transformations
long[] lengths = new long[26];
for (final char c : s.toCharArray())
++count[c - 'a'];
for (int i = 0; i < 26; ++i)
for (int j = 0; j < 26; ++j) {
lengths[j] += (long) count[i] * poweredT[i][j];
lengths[j] %= kMod;
}
return (int) (Arrays.stream(lengths).sum() % kMod);
}
private static final int kMod = 1_000_000_007;
private int[][] getTransformationMatrix(List<Integer> nums) {
int[][] T = new int[26][26];
for (int i = 0; i < nums.size(); ++i)
for (int step = 1; step <= nums.get(i); ++step)
++T[i][(i + step) % 26];
return T;
}
private int[][] getIdentityMatrix(int sz) {
int[][] I = new int[sz][sz];
for (int i = 0; i < sz; ++i)
I[i][i] = 1;
return I;
}
// Returns A * B.
private int[][] matrixMult(int[][] A, int[][] B) {
final int sz = A.length;
int[][] C = new int[sz][sz];
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j)
for (int k = 0; k < sz; ++k)
C[i][j] = (int) ((C[i][j] + (long) A[i][k] * B[k][j]) % kMod);
return C;
}
// Returns M^n.
private int[][] matrixPow(int[][] M, int n) {
if (n == 0)
return getIdentityMatrix(M.length);
if (n % 2 == 1)
return matrixMult(M, matrixPow(M, n - 1));
return matrixPow(matrixMult(M, M), n / 2);
}
} // code provided by PROGIEZ
3337. Total Characters in String After Transformations II LeetCode Solution in Python
class Solution:
# Similar to 3335. Total Characters in String After Transformations I
def lengthAfterTransformations(self, s: str, t: int, nums: list[int]) -> int:
kMod = 1_000_000_007
def matrixMult(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:
"""Returns A * B."""
sz = len(A)
C = [[0] * sz for _ in range(sz)]
for i in range(sz):
for j in range(sz):
for k in range(sz):
C[i][j] += A[i][k] * B[k][j]
C[i][j] %= kMod
return C
def matrixPow(M: list[list[int]], n: int) -> list[list[int]]:
"""Returns M^n."""
if n == 0:
return [[1 if i == j else 0 # identity matrix
for j in range(len(M))]
for i in range(len(M))]
if n % 2 == 1:
return matrixMult(M, matrixPow(M, n - 1))
return matrixPow(matrixMult(M, M), n // 2)
# T[i][j] := the number of ways to transform ('a' + i) to ('a' + j)
T = self._getTransformationMatrix(nums)
poweredT = matrixPow(T, t)
count = [0] * 26
lengths = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
for i in range(26):
for j in range(26):
lengths[j] += count[i] * poweredT[i][j]
lengths[j] %= kMod
return sum(lengths) % kMod
def _getTransformationMatrix(self, nums: list[int]) -> list[list[int]]:
T = [[0] * 26 for _ in range(26)]
for i, steps in enumerate(nums):
for step in range(1, steps + 1):
T[i][(i + step) % 26] += 1
return T # code by PROGIEZ
