Description
You are given a string s and an integer t, representing the number of transformations to perform. In one transformation, every character in s is replaced according to the following rules:
- If the character is
'z', replace it with the string"ab". - Otherwise, replace it with the next character in the alphabet. For example,
'a'is replaced with'b','b'is replaced with'c', and so on.
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
Output: 7
Explanation:
- First Transformation (t = 1):
<ul> <li><code>'a'</code> becomes <code>'b'</code></li> <li><code>'b'</code> becomes <code>'c'</code></li> <li><code>'c'</code> becomes <code>'d'</code></li> <li><code>'y'</code> becomes <code>'z'</code></li> <li><code>'y'</code> becomes <code>'z'</code></li> <li>String after the first transformation: <code>"bcdzz"</code></li> </ul> </li> <li><strong>Second Transformation (t = 2)</strong>: <ul> <li><code>'b'</code> becomes <code>'c'</code></li> <li><code>'c'</code> becomes <code>'d'</code></li> <li><code>'d'</code> becomes <code>'e'</code></li> <li><code>'z'</code> becomes <code>"ab"</code></li> <li><code>'z'</code> becomes <code>"ab"</code></li> <li>String after the second transformation: <code>"cdeabab"</code></li> </ul> </li> <li><strong>Final Length of the string</strong>: The string is <code>"cdeabab"</code>, which has 7 characters.</li>
Example 2:
Input: s = "azbk", t = 1
Output: 5
Explanation:
- First Transformation (t = 1):
<ul> <li><code>'a'</code> becomes <code>'b'</code></li> <li><code>'z'</code> becomes <code>"ab"</code></li> <li><code>'b'</code> becomes <code>'c'</code></li> <li><code>'k'</code> becomes <code>'l'</code></li> <li>String after the first transformation: <code>"babcl"</code></li> </ul> </li> <li><strong>Final Length of the string</strong>: The string is <code>"babcl"</code>, which has 5 characters.</li>
Constraints:
1 <= s.length <= 105sconsists only of lowercase English letters.1 <= t <= 105
Solution
Python3
class Solution:
def lengthAfterTransformations(self, s: str, t: int) -> int:
N = len(s)
M = 10 ** 9 + 7
counter = [0] * 26
for x in s:
counter[ord(x) - ord('a')] += 1
for _ in range(t):
newCounter = [0] * 26
for i in range(26):
if i != 25:
newCounter[i + 1] += counter[i]
newCounter[i + 1] %= M
else:
newCounter[0] += counter[i]
newCounter[1] += counter[i]
newCounter[0] %= M
newCounter[1] %= M
counter = newCounter
res = 0
for x in counter:
res += x
res %= M
return res