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 nextnums[s[i] - 'a']consecutive characters in the alphabet. For example, ifs[i] = 'a'andnums[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, ifs[i] = 'y'andnums[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):
<ul> <li><code>'a'</code> becomes <code>'b'</code> as <code>nums[0] == 1</code></li> <li><code>'b'</code> becomes <code>'c'</code> as <code>nums[1] == 1</code></li> <li><code>'c'</code> becomes <code>'d'</code> as <code>nums[2] == 1</code></li> <li><code>'y'</code> becomes <code>'z'</code> as <code>nums[24] == 1</code></li> <li><code>'y'</code> becomes <code>'z'</code> as <code>nums[24] == 1</code></li> <li>String after the first transformation: <code>"bcdzz"</code></li> </ul> </li> <li> <p><strong>Second Transformation (t = 2):</strong></p> <ul> <li><code>'b'</code> becomes <code>'c'</code> as <code>nums[1] == 1</code></li> <li><code>'c'</code> becomes <code>'d'</code> as <code>nums[2] == 1</code></li> <li><code>'d'</code> becomes <code>'e'</code> as <code>nums[3] == 1</code></li> <li><code>'z'</code> becomes <code>'ab'</code> as <code>nums[25] == 2</code></li> <li><code>'z'</code> becomes <code>'ab'</code> as <code>nums[25] == 2</code></li> <li>String after the second transformation: <code>"cdeabab"</code></li> </ul> </li> <li> <p><strong>Final Length of the string:</strong> The string is <code>"cdeabab"</code>, which has 7 characters.</p> </li>
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):
<ul> <li><code>'a'</code> becomes <code>'bc'</code> as <code>nums[0] == 2</code></li> <li><code>'z'</code> becomes <code>'ab'</code> as <code>nums[25] == 2</code></li> <li><code>'b'</code> becomes <code>'cd'</code> as <code>nums[1] == 2</code></li> <li><code>'k'</code> becomes <code>'lm'</code> as <code>nums[10] == 2</code></li> <li>String after the first transformation: <code>"bcabcdlm"</code></li> </ul> </li> <li> <p><strong>Final Length of the string:</strong> The string is <code>"bcabcdlm"</code>, which has 8 characters.</p> </li>
Constraints:
1 <= s.length <= 105sconsists only of lowercase English letters.1 <= t <= 109nums.length == 261 <= nums[i] <= 25
Solution
Python3
class Solution:
def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
MOD = 10 ** 9 + 7
def mult(matA, matB):
Ra, Ca = len(matA), len(matA[0])
Rb, Cb = len(matB), len(matB[0])
assert Ca == Rb, "Matrix mult not possible, dimensions don't match"
Rc = Ra
Cc = Cb
result = [[0 for _ in range(Cc)] for _ in range(Rc)]
for i in range(Rc):
for j in range(Cc):
for k in range(Rb):
result[i][j] += (matA[i][k] * matB[k][j]) % MOD
return result
def mat_pow(mat, power):
if power == 1:
return mat
broke = mat_pow(mat, power // 2)
if power & 1:
return mult(mat, mult(broke, broke))
return mult(broke, broke)
freqs = [[0 for _ in range(26)]]
for ch in s:
freqs[0][ord(ch) - 97] += 1
transform = [[0 for _ in range(26)] for _ in range(26)]
for i in range(26):
for x in range(i + 1, i + nums[i] + 1):
transform[i][x % 26] += 1
res = mult(freqs, mat_pow(transform, t))
return sum(res[0]) % MOD