LeetCode Problem 3337

Difficulty: 🔴 Hard
Topics: Hash Table, Math, String, Dynamic Programming, Counting

Solution

Problem Understanding

The problem defines a repeated string transformation process over lowercase English letters. Every character does not simply become one new character, instead it expands into multiple characters depending on the value stored in nums.

For a character c, let its alphabet index be:

• 'a' -> 0
• 'b' -> 1
• ...
• 'z' -> 25

If nums[index] = k, then the character transforms into the next k consecutive letters in the alphabet, wrapping around if necessary.

For example:

• 'a' with k = 3 becomes "bcd"
• 'y' with k = 3 becomes "zab"

This transformation is applied simultaneously to every character in the string, and we repeat the process exactly t times.

The task is not to construct the final string itself. The final string can become astronomically large because each character may expand into many characters during every transformation. Instead, we only need the final length modulo 10^9 + 7.

The constraints immediately reveal that brute force simulation is impossible:

• s.length can be up to 10^5
• t can be as large as 10^9

Even if each character expanded only slightly, the resulting string size after many transformations would be enormous.

The key observation is that the actual character order does not matter for the final answer. We only care about how many characters each letter eventually contributes after a certain number of transformations.

Several edge cases are important:

• Very large t, which rules out linear simulation over transformations.
• Wrapping around the alphabet from 'z' back to 'a'.
• Different letters having different expansion counts.
• Cases where every letter expands to many letters, causing exponential growth.
• Strings containing repeated letters, where recomputing the same transformation repeatedly would be wasteful.

The problem guarantees:

• nums[i] >= 1, so every character always produces at least one character.
• nums[i] <= 25, meaning a letter never expands into the full alphabet.
• Only lowercase English letters are involved, which means the state space is fixed at size 26.

Because the alphabet size is constant, matrix exponentiation becomes a natural fit.

Approaches

Brute Force Approach

The most direct solution is to literally simulate the transformations.

For each transformation:

1. Create a new string.
2. For every character in the current string:

• Look up nums.
• Append the appropriate consecutive characters.

3. Replace the old string with the new one.

This approach is correct because it follows the transformation rules exactly.

However, it becomes infeasible extremely quickly. The string length can grow exponentially. Even with small expansion factors, after many transformations the string becomes impossibly large.

For example, if every character doubles in size, after t = 50 transformations the size would already exceed 2^50.

Since t can reach 10^9, brute force is completely impossible.

Key Insight

Instead of tracking the actual string, we track how many characters each letter contributes after a given number of transformations.

Define:

• dp[t][c] = number of characters produced after applying t transformations starting from character c.

Suppose character c expands into several next characters:

$$c \rightarrow c_1, c_2, ..., c_k$$

Then:

$$dp[t][c] = dp[t-1][c_1] + dp[t-1][c_2] + ... + dp[t-1][c_k]$$

This is a linear recurrence over only 26 states.

That means we can model the transformation using a 26 x 26 transition matrix.

If:

$$V_t$$

represents the contribution vector after t transformations, then:

$$V_t = M^t \cdot V_0$$

where:

• M is the transition matrix
• V_0 is the base vector where every character contributes length 1 before any transformations

Since the alphabet size is fixed at 26, matrix exponentiation is extremely efficient:

$$O(26^3 \log t)$$

which is easily fast enough.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explicitly builds transformed strings
Optimal	O(26³ log t + n)	O(26²)	Uses matrix exponentiation on fixed-size alphabet

Algorithm Walkthrough

1. Create a 26 x 26 transition matrix.

Each row represents a source character. Each column represents a destination character.

If character i transforms into the next nums[i] characters, then for every reachable character j, we add:

$$M[i][j] = 1$$

For example, if 'a' expands into "bcd", then:

$$M[0][1] = 1,\quad M[0][2] = 1,\quad M[0][3] = 1$$ 2. Define the base contribution vector.

Before any transformations, every character contributes exactly one character to the final length.

So:

$$base = [1,1,1,...,1]$$ 3. Compute the matrix power.

We need:

$$M^t$$

Since t may be as large as 10^9, we use binary exponentiation. 4. Multiply the powered matrix by the base vector.

This gives the number of final characters contributed by each starting letter after t transformations. 5. Count frequencies of characters in the input string.

For each character in s, determine how many final characters it contributes. 6. Sum all contributions modulo 10^9 + 7.

Why it works

The transformation process is linear. Every character independently expands into a fixed set of next characters. The total contribution after multiple transformations is therefore the repeated application of the same linear transition rule.

Matrix multiplication naturally models repeated linear transitions. Raising the transition matrix to the power t computes exactly how each letter evolves after t transformations. Since every character contributes independently, summing the contributions for all characters in the original string produces the correct final length.

Python Solution

from typing import List

MOD = 10**9 + 7

class Solution:
    def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
        SIZE = 26

        def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
            result = [[0] * SIZE for _ in range(SIZE)]

            for i in range(SIZE):
                for k in range(SIZE):
                    if a[i][k] == 0:
                        continue

                    for j in range(SIZE):
                        result[i][j] = (
                            result[i][j] + a[i][k] * b[k][j]
                        ) % MOD

            return result

        def matrix_power(matrix: List[List[int]], power: int) -> List[List[int]]:
            result = [[0] * SIZE for _ in range(SIZE)]

            for i in range(SIZE):
                result[i][i] = 1

            while power > 0:
                if power & 1:
                    result = multiply(result, matrix)

                matrix = multiply(matrix, matrix)
                power >>= 1

            return result

        transition = [[0] * SIZE for _ in range(SIZE)]

        for i in range(SIZE):
            for step in range(1, nums[i] + 1):
                nxt = (i + step) % SIZE
                transition[i][nxt] += 1

        powered = matrix_power(transition, t)

        contribution = [0] * SIZE

        for i in range(SIZE):
            total = 0

            for j in range(SIZE):
                total = (total + powered[i][j]) % MOD

            contribution[i] = total

        answer = 0

        for ch in s:
            answer = (
                answer + contribution[ord(ch) - ord('a')]
            ) % MOD

        return answer

The implementation begins by defining matrix multiplication for fixed-size 26 x 26 matrices. Since matrix exponentiation repeatedly multiplies matrices together, this helper function is central to the solution.

The multiplication function uses the standard triple-loop algorithm. An optimization skips work whenever a[i][k] is zero.

Next, binary exponentiation computes matrix^t. The identity matrix is used as the initial result because multiplying by the identity matrix preserves values.

The transition matrix is then constructed directly from the transformation rules. Every row corresponds to one source character, and every valid transformed character receives a count of 1.

After exponentiation, each row of the powered matrix tells us how many copies of each letter are produced from a starting character after t transformations. Since we only care about total length, we sum each row.

Finally, we iterate through the original string and accumulate the contribution of every character.

Go Solution

package main

const MOD int = 1_000_000_007
const SIZE int = 26

func multiply(a [][]int, b [][]int) [][]int {
	result := make([][]int, SIZE)

	for i := 0; i < SIZE; i++ {
		result[i] = make([]int, SIZE)
	}

	for i := 0; i < SIZE; i++ {
		for k := 0; k < SIZE; k++ {
			if a[i][k] == 0 {
				continue
			}

			for j := 0; j < SIZE; j++ {
				result[i][j] = (result[i][j] +
					a[i][k]*b[k][j]) % MOD
			}
		}
	}

	return result
}

func matrixPower(matrix [][]int, power int) [][]int {
	result := make([][]int, SIZE)

	for i := 0; i < SIZE; i++ {
		result[i] = make([]int, SIZE)
		result[i][i] = 1
	}

	for power > 0 {
		if power&1 == 1 {
			result = multiply(result, matrix)
		}

		matrix = multiply(matrix, matrix)
		power >>= 1
	}

	return result
}

func lengthAfterTransformations(s string, t int, nums []int) int {
	transition := make([][]int, SIZE)

	for i := 0; i < SIZE; i++ {
		transition[i] = make([]int, SIZE)
	}

	for i := 0; i < SIZE; i++ {
		for step := 1; step <= nums[i]; step++ {
			next := (i + step) % SIZE
			transition[i][next]++
		}
	}

	powered := matrixPower(transition, t)

	contribution := make([]int, SIZE)

	for i := 0; i < SIZE; i++ {
		total := 0

		for j := 0; j < SIZE; j++ {
			total = (total + powered[i][j]) % MOD
		}

		contribution[i] = total
	}

	answer := 0

	for _, ch := range s {
		answer = (answer +
			contribution[int(ch-'a')]) % MOD
	}

	return answer
}

The Go implementation follows the same structure as the Python version, but uses slices instead of lists.

One important detail is modular arithmetic. Go integers can overflow more easily depending on architecture, but because every multiplication is reduced modulo MOD immediately, values remain safe.

The matrix structures are represented as [][]int, and explicit allocation is required before use.

Worked Examples

Example 1

Input:

s = "abcyy"
t = 2
nums = [1,1,1,...,1,2]

Step 1: Build Transition Rules

Most letters transform into exactly one next letter.

Examples:

Letter	Transformation
a	b
b	c
c	d
y	z
z	ab

Step 2: Compute Contributions After 2 Transformations

Start Letter	After 1 Step	After 2 Steps	Final Length
a	b	c	1
b	c	d	1
c	d	e	1
y	z	ab	2
z	ab	bc	2

Step 3: Sum Contributions

Character	Contribution
a	1
b	1
c	1
y	2
y	2

Total:

$$1 + 1 + 1 + 2 + 2 = 7$$

Answer:

7

Example 2

Input:

s = "azbk"
t = 1
nums = [2,2,2,...,2]

Step 1: Every Letter Expands Into 2 Letters

Examples:

Letter	Transformation
a	bc
z	ab
b	cd
k	lm

Step 2: Contribution After One Transformation

Every character contributes exactly 2 characters.

Character	Contribution
a	2
z	2
b	2
k	2

Total:

$$2 + 2 + 2 + 2 = 8$$

Answer:

8

Complexity Analysis

Measure	Complexity	Explanation
Time	O(26³ log t + n)	Matrix exponentiation plus processing the input string
Space	O(26²)	Stores several 26 x 26 matrices

The dominant cost comes from matrix multiplication during exponentiation. Since the matrix size is fixed at 26, the practical runtime is very small.

Binary exponentiation performs only O(log t) matrix multiplications, which makes even t = 10^9 manageable.

Test Cases

sol = Solution()

# Provided example 1
assert sol.lengthAfterTransformations(
    "abcyy",
    2,
    [1] * 25 + [2]
) == 7

# Provided example 2
assert sol.lengthAfterTransformations(
    "azbk",
    1,
    [2] * 26
) == 8

# Single character, no branching
assert sol.lengthAfterTransformations(
    "a",
    1,
    [1] * 26
) == 1

# Single character, repeated doubling
assert sol.lengthAfterTransformations(
    "a",
    3,
    [2] * 26
) == 8

# Wrapping around alphabet
assert sol.lengthAfterTransformations(
    "z",
    1,
    [1] * 25 + [2]
) == 2

# Multiple repeated characters
assert sol.lengthAfterTransformations(
    "aaaa",
    2,
    [2] * 26
) == 16

# Large t with minimal growth
assert sol.lengthAfterTransformations(
    "abc",
    10**9,
    [1] * 26
) == 3

# Every character expands maximally
assert sol.lengthAfterTransformations(
    "abc",
    2,
    [25] * 26
) > 0

# Entire alphabet input
assert sol.lengthAfterTransformations(
    "abcdefghijklmnopqrstuvwxyz",
    1,
    [1] * 26
) == 26

# Mixed expansion sizes
assert sol.lengthAfterTransformations(
    "abc",
    2,
    list(range(1, 27))
) > 0

Test	Why
Example 1	Validates wrapping and mixed expansion
Example 2	Validates uniform expansion
Single character minimal	Smallest non-trivial input
Repeated doubling	Checks exponential growth handling
Wraparound from z	Ensures modulo alphabet indexing works
Repeated characters	Confirms additive contribution logic
Very large t	Verifies logarithmic exponentiation
Maximum branching	Stresses matrix growth
Entire alphabet	Ensures all states behave correctly
Mixed nums values	Tests irregular transitions

Edge Cases

Very Large Transformation Count

The most dangerous input is a huge value of t, especially near 10^9. Any solution that iterates transformation-by-transformation will timeout immediately.

The implementation handles this using binary exponentiation. Instead of performing t matrix multiplications, it performs only O(log t) multiplications.

Alphabet Wraparound

Characters near the end of the alphabet can wrap back to the beginning.

For example:

'y' -> "zab"
'z' -> "ab"

This is a common source of indexing bugs. The implementation safely handles wraparound using:

(i + step) % 26

which guarantees the destination character index always remains valid.

Explosive String Growth

Some inputs cause exponential expansion. For example, if every character expands into 25 characters, the true final string size becomes unimaginably large after even modest values of t.

The implementation never constructs the actual string. It only tracks aggregate counts through matrix operations, which keeps memory usage constant regardless of theoretical string size.