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 II

Number: 3630

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string s (of lowercase English letters), an integer t representing the number of transformations, and an array nums of size 26, perform t transformations on s where each character c in s is replaced by the next nums[c - 'a'] consecutive characters in the alphabet (wrapping around from 'z' to 'a'). The task is to return the length of the final string after exactly t transformations modulo 10^9+7.

Key Insights

  • Each character expands into a substring whose length depends on the corresponding value in nums.
  • The transformation is applied simultaneously to every character and is recursive in nature.
  • For t transformations, we can think in terms of a recurrence: f(c, t) = (sum of f(nextChar, t - 1)) over the next nums[c-'a'] characters.
  • Instead of simulating transformations (which is infeasible for large t), we can compute the total length using matrix exponentiation.
  • Construct a 26x26 matrix A where row i represents the transition from letter i to the letters produced by its transformation.
  • The final result is obtained by computing A^t multiplied by a base vector of ones (since each letter initially contributes a length of 1) and then summing the contributions according to the frequency of each letter in s.

Space and Time Complexity

Time Complexity: O(26^3 * log t) – matrix exponentiation on a 26x26 matrix. Space Complexity: O(26^2) – for storing the matrix.

Solution

We reduce the problem to computing a recurrence using matrix exponentiation. First, represent the transformation as a 26x26 matrix A where for each letter with index i (0-indexed for 'a'), for j = 1 to nums[i] we set A[i][(i + j) mod 26] = 1. This matrix encodes how one instance of a letter expands into several letters. Let the base vector B be a 26-dimensional vector of all 1’s, representing that a letter (when no transformation is applied) contributes a count of 1.

After one transformation, the contribution of letter i is given by the dot product:   f(i, 1) = sum over j of A[i][j] * 1. After applying t transformations, the contribution vector becomes:   v = A^t * B.

To get the final length for the string s, count the frequency of each letter in s (forming a vector F) and compute:   answer = F dot v, taking the answer modulo 10^9+7.

This approach efficiently computes the result even when t is large (up to 10^9).

Code Solutions

MOD = 10**9 + 7

# Function to multiply two 26x26 matrices
def mat_mul(A, B):
    size = 26
    C = [[0]*size for _ in range(size)]
    for i in range(size):
        for k in range(size):
            if A[i][k]:
                for j in range(size):
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
    return C

# Function to exponentiate matrix A to power p
def mat_pow(A, p):
    size = 26
    # Initialize result as Identity matrix
    result = [[1 if i == j else 0 for j in range(size)] for i in range(size)]
    while p:
        if p & 1:
            result = mat_mul(result, A)
        A = mat_mul(A, A)
        p //=  2
    return result

def totalCharacters(s, t, nums):
    size = 26
    # Build the transformation matrix A
    A = [[0]*size for _ in range(size)]
    for i in range(size):
        # For letter corresponding to index i, it becomes the next nums[i] letters (wrap around)
        for j in range(1, nums[i] + 1):
            next_index = (i + j) % size
            A[i][next_index] = 1

    # Exponentiate A to the t-th power
    A_t = mat_pow(A, t)
    
    # The base vector B: every letter counts as 1 when t = 0.
    base = [1] * size
    
    # Multiply A^t with B to get the expansion counts for each letter
    expansion = [0] * size
    for i in range(size):
        for j in range(size):
            expansion[i] = (expansion[i] + A_t[i][j] * base[j]) % MOD

    # Count letter frequencies in s and use them to sum the contributions.
    freq = [0] * size
    for ch in s:
        freq[ord(ch) - ord('a')] += 1

    result = 0
    for i in range(size):
        result = (result + freq[i] * expansion[i]) % MOD

    return result

# Example usage:
if __name__ == '__main__':
    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]
    print(totalCharacters(s, t, nums))  # Expected output: 7
← Back to All Questions