Introduction

In this blog post, we will explore how to solve the LeetCode problem "3337" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You are given a string s consisting of lowercase English letters, an integer t representing the number of transformations to perform, and an array nums of size 26. In one transformation, every character in s is replaced according to the following rules: Replace s[i] with the next nums[s[i] - 'a'] consecutive characters in the alphabet. For example, if s[i] = 'a' and nums[0] = 3, the character 'a' transforms into the next 3 consecutive characters ahead of it, which results in "bcd". The transformation wraps around the alphabet if it exceeds 'z'. For example, if s[i] = 'y' and nums[24] = 3, the character 'y' transforms into the next 3 consecutive characters ahead of it, which results in "zab". 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, 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] Output: 7 Explanation: First Transformation (t = 1): 'a' becomes 'b' as nums[0] == 1 'b' becomes 'c' as nums[1] == 1 'c' becomes 'd' as nums[2] == 1 'y' becomes 'z' as nums[24] == 1 'y' becomes 'z' as nums[24] == 1 String after the first transformation: "bcdzz" Second Transformation (t = 2): 'b' becomes 'c' as nums[1] == 1 'c' becomes 'd' as nums[2] == 1 'd' becomes 'e' as nums[3] == 1 'z' becomes 'ab' as nums[25] == 2 'z' becomes 'ab' as nums[25] == 2 String after the second transformation: "cdeabab" Final Length of the string: The string is "cdeabab", which has 7 characters. Example 2: Input: s = "azbk", t = 1, nums = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] Output: 8 Explanation: First Transformation (t = 1): 'a' becomes 'bc' as nums[0] == 2 'z' becomes 'ab' as nums[25] == 2 'b' becomes 'cd' as nums[1] == 2 'k' becomes 'lm' as nums[10] == 2 String after the first transformation: "bcabcdlm" Final Length of the string: The string is "bcabcdlm", which has 8 characters. Constraints: 1 <= s.length <= 105 s consists only of lowercase English letters. 1 <= t <= 109 nums.length == 26 1 <= nums[i] <= 25

Explanation

Here's a breakdown of the solution:

• Matrix Representation: Model the character transformations as matrix multiplications. Each character's transformation is represented by a 26x26 matrix, and repeated transformations can be efficiently computed using matrix exponentiation.
• Length Calculation: Calculate the final length by summing the contributions of each initial character after applying the transformations. Each character contributes to the final length based on how its transformation expands over t iterations.

• Modular Arithmetic: Apply the modulo operator (10^9 + 7) throughout the calculations to prevent integer overflow and ensure the result stays within the required range.

• Runtime Complexity: O(26^3 * log(t) + n), where n is the length of string s. Storage Complexity: O(26^2).

Code

    def solve():
    s = input()
    t = int(input())
    nums = list(map(int, input().split()))
    MOD = 10**9 + 7

    def matrix_multiply(A, B):
        C = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for j in range(26):
                for k in range(26):
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
        return C

    def matrix_power(A, n):
        result = [[0] * 26 for _ in range(26)]
        for i in range(26):
            result[i][i] = 1
        while n > 0:
            if n % 2 == 1:
                result = matrix_multiply(result, A)
            A = matrix_multiply(A, A)
            n //= 2
        return result

    initial_lengths = [0] * 26
    for char in s:
        initial_lengths[ord(char) - ord('a')] += 1

    transformation_matrix = [[0] * 26 for _ in range(26)]
    for i in range(26):
        for j in range(nums[i]):
            transformation_matrix[i][(i + 1 + j) % 26] = 1

    final_transformation_matrix = matrix_power(transformation_matrix, t)

    final_lengths = [0] * 26
    for i in range(26):
        for j in range(26):
            final_lengths[j] = (final_lengths[j] + initial_lengths[i] * final_transformation_matrix[i][j]) % MOD

    total_length = sum(final_lengths) % MOD
    print(total_length)

solve()