Total Characters in String After Transformations I Solution
Total Characters in String After Transformations I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Total Characters in String After Transformations I is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Dynamic Programming, Math, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of lowercase letters and an integer t, the number of transformations to perform.
In one transformation, every character of s is replaced at the same time:
'z'becomes the two-character string"ab";- every other character becomes the next letter of the alphabet (
'a'becomes'b','b'becomes'c', and so on).
Return the length of the string after exactly t transformations. Since it may be very large, return it modulo 10^9 + 7.
Example 1
Input: s = "abcyy", t = 2
Output: 7
Explanation: After one step: "bcdzz". After two: "cdeabab", which has 7 characters.
Example 2
Input: s = "azbk", t = 1
Output: 5
Explanation: One step gives "babcl".
Example 3
Input: s = "a", t = 26
Output: 2
Explanation: Twenty-five steps take 'a' to 'z'; the 26th turns it into "ab".
Constraints
1 <= s.length <= 10^5s consists only of lowercase English letters1 <= t <= 10^5
Hints for Total Characters in String After Transformations I
Hint 1
The order of the characters never matters for the length — only how many of each letter there are.
Hint 2
Keep a count for each of the 26 letters. One transformation shifts every count one letter up; the count of
'z'moves to both'a'and'b'.Hint 3
Apply that shift
ttimes, keeping every count modulo10^9 + 7, and add the counts up at the end.
How to solve Total Characters in String After Transformations I
Characters transform independently, so the string can be replaced by a histogram of 26 counts. A transformation is a fixed linear map on that histogram: each letter's count moves to the next letter, and 'z''s count is added to both 'a' and 'b'.
Approach
- Count the occurrences of each letter in
s. - Repeat
ttimes:new[0] = cnt[25],new[1] = cnt[0] + cnt[25], andnew[c] = cnt[c - 1]forc >= 2, all modulo10^9 + 7. - Return the sum of the counts modulo
10^9 + 7.
Why it works
A character's descendants after any number of steps depend only on the character itself, never on its neighbours, so grouping equal letters loses nothing. The map above is exactly one step applied to every group at once.
Complexity
- Time —
O(|s| + 26 · t) - Space —
O(26)
Pitfalls
- Build the new counts from the old ones (or rotate carefully) — updating in place would move a count twice in one step.
- The length grows exponentially (roughly doubling every 26 steps), so reduce modulo
10^9 + 7at every step.
Reference solution
Python
def lengthAfterTransformations(s: str, t: int) -> int:
MOD = 10**9 + 7
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - 97] += 1
for _ in range(t):
z = cnt[25]
cnt = [z] + cnt[:25]
cnt[1] = (cnt[1] + z) % MOD
return sum(cnt) % MODJava
public static int lengthAfterTransformations(String s, int t) {
final long MOD = 1000000007L;
long[] cnt = new long[26];
for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
for (int step = 0; step < t; step++) {
long z = cnt[25];
for (int c = 25; c >= 1; c--) cnt[c] = cnt[c - 1];
cnt[0] = z;
cnt[1] = (cnt[1] + z) % MOD;
}
long total = 0;
for (long x : cnt) total = (total + x) % MOD;
return (int) total;
}C++
int lengthAfterTransformations(string s, int t) {
const long long MOD = 1000000007LL;
long long cnt[26] = {0};
for (char ch : s) cnt[ch - 'a']++;
for (int step = 0; step < t; step++) {
long long z = cnt[25];
for (int c = 25; c >= 1; c--) cnt[c] = cnt[c - 1];
cnt[0] = z;
cnt[1] = (cnt[1] + z) % MOD;
}
long long total = 0;
for (int c = 0; c < 26; c++) total = (total + cnt[c]) % MOD;
return (int) total;
}JavaScript
var lengthAfterTransformations = function(s, t) {
var MOD = 1000000007;
var cnt = new Array(26).fill(0);
for (var i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
for (var step = 0; step < t; step++) {
var z = cnt[25];
for (var c = 25; c >= 1; c--) cnt[c] = cnt[c - 1];
cnt[0] = z;
cnt[1] = (cnt[1] + z) % MOD;
}
var total = 0;
for (var j = 0; j < 26; j++) total = (total + cnt[j]) % MOD;
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets