We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Total Characters in String After Transformations I

Number: 3629

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a string s and an integer t, perform exactly t transformations on s. In each transformation, every character is replaced as follows:

  • If a character is 'z', replace it with "ab".
  • Otherwise, replace it with the next character in the alphabet. Return the length of the resulting string after t transformations modulo 10^9+7.

Key Insights

  • For characters other than 'z', the transformation always produces one character by simply moving to the next character.
  • For a character c ≠ 'z', if t is less than the distance from c to 'z' (i.e. 'z' - c), then that character never reaches 'z' and contributes length 1.
  • If t is at least the distance d = ('z' - c), then after d transformations, c becomes 'z'. From that point on, the remaining t-d transformations follow the recurrence for 'z'.
  • When a 'z' is transformed, it generates "ab", which then evolves separately in future transformations.
  • Thus, the problem reduces to computing a function dp[k] which gives the final length if we start from 'z' and perform k transformations.
  • The recurrence for dp is:
    • dp[0] = 1 (0 transformations yields a single character)
    • For k ≥ 1, dp[k] = (dp[k-1-25] if k-1 ≥ 25 else 1) + (dp[k-1-24] if k-1 ≥ 24 else 1) This stems from the fact that: a. 'z' transforms into "ab", so one branch comes from 'a' and the other from 'b'. b. For letter 'a', it will become 'z' after 25 transformations; for 'b' after 24.
  • Sum the contributions for each character in s: For a character c, if t < (z - c) then it contributes 1; Otherwise its contribution is dp[t - (z - c)].

Space and Time Complexity

Time Complexity: O(t + |s|) because we precompute dp for t transformations (O(t)) and then process each character in s (O(|s|)). Space Complexity: O(t) for storing the dp array.

Solution

We use dynamic programming to precompute dp[k] for every k from 0 to t representing the final length from a 'z' after k transformations. For each character in the string, we calculate its distance d from 'z'. If t < d, the character never reaches 'z', so it contributes 1. Otherwise, it contributes dp[t - d]. Finally, we sum all contributions modulo 10^9+7.

We use arrays (or equivalent) to store dp values and simple arithmetic to build the solution.

Code Solutions

# Define the modulo constant.
MOD = 10**9 + 7

def total_transformed_length(s, t):
    # Precompute dp[i]: length resulting from 'z' after i transformations.
    dp = [0] * (t + 1)
    dp[0] = 1  # 0 transformations yield length 1.
    for i in range(1, t + 1):
        # For transforming 'z', we replace it with "ab", i.e., 
        # contribution from 'a': if (i-1) < 25, then it has not reached 'z' so length = 1; else, dp[i-1-25]
        if i - 1 < 25:
            contrib_a = 1
        else:
            contrib_a = dp[i - 1 - 25]
        # For letter 'b': if (i-1) < 24, then length = 1; else, dp[i-1-24]
        if i - 1 < 24:
            contrib_b = 1
        else:
            contrib_b = dp[i - 1 - 24]
        dp[i] = (contrib_a + contrib_b) % MOD
    
    total_len = 0
    for char in s:
        d = ord('z') - ord(char)  # Distance from current char to 'z'
        if t < d:
            # Not enough transformations to reach 'z'
            total_len = (total_len + 1) % MOD
        else:
            # After d steps, char becomes 'z', then remaining transformations t-d.
            total_len = (total_len + dp[t - d]) % MOD
    return total_len

# Example usage:
print(total_transformed_length("abcyy", 2))  # Expected output: 7
print(total_transformed_length("azbk", 1))   # Expected output: 5
← Back to All Questions