Total Characters in String After Transformations I

Medium
1667.

Total Characters in String After Transformations I

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.

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^5
  • s consists only of lowercase English letters
  • 1 <= t <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} t
 * @return {number}
 */
var lengthAfterTransformations = function(s, t) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • s consists only of lowercase English letters
  • 1 <= t <= 10^5

Hints for Total Characters in String After Transformations I

  1. Hint 1

    The order of the characters never matters for the length — only how many of each letter there are.

  2. 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'.

  3. Hint 3

    Apply that shift t times, keeping every count modulo 10^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

  1. Count the occurrences of each letter in s.
  2. Repeat t times: new[0] = cnt[25], new[1] = cnt[0] + cnt[25], and new[c] = cnt[c - 1] for c >= 2, all modulo 10^9 + 7.
  3. 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 + 7 at 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) % MOD

Java

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