3337. Total Characters in String After Transformations II
Problem Description
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 each transformation, every character in the string is replaced according to specific rules:
- Each character
s[i]
is replaced with the nextnums[s[i] - 'a']
consecutive characters in the alphabet. For example:- If
s[i] = 'a'
andnums[0] = 3
, the character'a'
transforms into the next 3 consecutive characters ahead of it, resulting in"bcd"
- If
- The transformation wraps around the alphabet if it goes beyond
'z'
. For example:- If
s[i] = 'y'
andnums[24] = 3
, the character'y'
transforms into the next 3 consecutive characters ahead of it, which wraps around to give"zab"
- If
The task is to determine the length of the resulting string after performing exactly t
transformations on the original string s
.
Since the answer can be very large, return it modulo 10^9 + 7
.
The key insight is that each transformation can significantly increase the string length - a single character can expand into multiple characters based on the corresponding value in nums
. After t
transformations, the string length could grow exponentially, making direct simulation impractical for large values of t
. The solution uses matrix exponentiation to efficiently compute the final character frequencies after all transformations, then sums them to get the total length.
Intuition
The first observation is that we don't need to track the actual string content - we only need to count how many of each character we have. Each character transforms independently based on its position in the alphabet.
Let's think about what happens in one transformation. If we have 5 'a's and nums[0] = 3
, then each 'a' becomes "bcd". So after one transformation, we get 5 'b's, 5 'c's, and 5 'd's from those original 'a's. This suggests we can track character frequencies instead of the actual string.
We can represent this transformation as a relationship: the count of each character after transformation depends on the counts of all characters before transformation. For character i
, it contributes to characters (i+1) % 26
, (i+2) % 26
, ..., (i+nums[i]) % 26
.
This relationship can be expressed as matrix multiplication. We create a transformation matrix M
where M[i][j] = 1
if character i
transforms to include character j
, and 0
otherwise. Then, if we have a frequency vector cnt
representing current character counts, cnt * M
gives us the character counts after one transformation.
For t
transformations, we need to compute cnt * M * M * ... * M
(t times), which is cnt * M^t
. Computing M^t
directly would take O(t) matrix multiplications, which is too slow for large t
.
The key insight is to use fast matrix exponentiation. Just like we can compute x^n
in O(log n) time using binary exponentiation (x^8 = ((x^2)^2)^2
), we can compute M^t
in O(log t) matrix multiplications. This reduces the time complexity from O(t) to O(log t), making it feasible even for very large values of t
.
Finally, the length of the resulting string is simply the sum of all character frequencies after t
transformations.
Learn more about Math and Dynamic Programming patterns.
Solution Approach
The solution uses fast matrix exponentiation to accelerate the recurrence relationship. Let's break down the implementation:
1. Initialize Character Frequency Count
First, we count the frequency of each character in the input string s
:
cnt = [0] * 26
for c in s:
cnt[ord(c) - ord("a")] += 1
2. Build the Transformation Matrix
We create a 26×26 transformation matrix where matrix[i][j] = 1
if character i
(0-indexed) transforms to include character j
:
matrix = [[0] * 26 for _ in range(26)]
for i, x in enumerate(nums):
for j in range(1, x + 1):
matrix[i][(i + j) % 26] = 1
For example, if nums[0] = 3
(character 'a' expands to 3 characters), then matrix[0][1] = matrix[0][2] = matrix[0][3] = 1
, meaning 'a' transforms to 'b', 'c', and 'd'.
3. Matrix Multiplication Function
The matmul
function multiplies two matrices with modulo operations to prevent overflow:
def matmul(a, b):
n, p, q = len(a), len(b), len(b[0])
res = [[0] * q for _ in range(n)]
for i in range(n):
for k in range(p):
if a[i][k]: # Optimization: skip if zero
for j in range(q):
res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod
return res
4. Fast Matrix Exponentiation
The matpow
function computes matrix^t
using binary exponentiation:
def matpow(mat, power):
res = [[int(i == j) for j in range(26)] for i in range(26)] # Identity matrix
while power:
if power % 2:
res = matmul(res, mat)
mat = matmul(mat, mat)
power //= 2
return res
This reduces the time complexity from O(t) to O(log t). The algorithm works by:
- Starting with an identity matrix as the result
- If the current bit of
power
is 1, multiply the result by the current matrix - Square the matrix for the next bit position
- Repeat until all bits are processed
5. Apply Transformations and Calculate Result
Finally, we compute the character frequencies after t
transformations:
cnt = [cnt] # Convert to 1×26 matrix
factor = matpow(matrix, t) # Get matrix^t
result = matmul(cnt, factor)[0] # Apply transformations
ans = sum(result) % mod # Sum all frequencies
The multiplication cnt * matrix^t
gives us the frequency of each character after t
transformations. The sum of these frequencies is the total length of the resulting string.
Time Complexity: O(26³ × log t) for matrix exponentiation Space Complexity: O(26²) for storing matrices
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Input: s = "ab"
, t = 2
, nums = [1, 2, 0, 0, ..., 0]
(remaining values are 0)
Step 1: Count initial character frequencies
- 'a' appears 1 time
- 'b' appears 1 time
- Frequency vector:
cnt = [1, 1, 0, 0, ..., 0]
Step 2: Build transformation matrix
- 'a' (index 0) with
nums[0] = 1
transforms to the next 1 character → 'b' - 'b' (index 1) with
nums[1] = 2
transforms to the next 2 characters → 'c', 'd' - All other characters have
nums[i] = 0
, so they don't transform
Transformation matrix (showing only first 4×4 for clarity):
a b c d a [[ 0 1 0 0 ] b [ 0 0 1 1 ] c [ 0 0 0 0 ] d [ 0 0 0 0 ]]
Step 3: First transformation (t=1)
Apply cnt × matrix
:
- 'a' (count=1) → produces 1 'b'
- 'b' (count=1) → produces 1 'c' and 1 'd'
- Result after 1 transformation:
[0, 1, 1, 1, 0, ..., 0]
- String would be "bcd" (length = 3)
Step 4: Second transformation (t=2)
We need matrix²
for two transformations.
Computing matrix²
:
a b c d a [[ 0 0 1 1 ] b [ 0 0 0 0 ] c [ 0 0 0 0 ] d [ 0 0 0 0 ]]
Apply original cnt × matrix²
:
- Original 'a' (count=1) → after 2 transformations produces 1 'c' and 1 'd'
- Original 'b' (count=1) → after 2 transformations produces nothing (since 'c' and 'd' have nums=0)
- Final frequency:
[0, 0, 1, 1, 0, ..., 0]
- String would be "cd" (length = 2)
Result: The length after 2 transformations is 2.
This example demonstrates how:
- We track character frequencies instead of the actual string
- The transformation matrix encodes how each character expands
- Matrix exponentiation efficiently computes multiple transformations
- The final length is the sum of all character frequencies
Solution Implementation
1class Solution:
2 def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:
3 """
4 Calculate the total length of string after t transformations.
5 Each character can transform into multiple characters based on nums array.
6
7 Args:
8 s: Initial string
9 t: Number of transformations to perform
10 nums: Array where nums[i] indicates character 'a'+i transforms to next nums[i] characters
11
12 Returns:
13 Total length after transformations modulo 10^9 + 7
14 """
15 MOD = 10**9 + 7
16 ALPHABET_SIZE = 26
17
18 # Count frequency of each character in the initial string
19 char_counts = [0] * ALPHABET_SIZE
20 for char in s:
21 char_index = ord(char) - ord('a')
22 char_counts[char_index] += 1
23
24 # Build transformation matrix
25 # transformation_matrix[i][j] = 1 if character i can transform to character j
26 transformation_matrix = [[0] * ALPHABET_SIZE for _ in range(ALPHABET_SIZE)]
27 for char_idx, transform_count in enumerate(nums):
28 # Character at index char_idx transforms into the next transform_count characters
29 for offset in range(1, transform_count + 1):
30 target_idx = (char_idx + offset) % ALPHABET_SIZE
31 transformation_matrix[char_idx][target_idx] = 1
32
33 def matrix_multiply(matrix_a: List[List[int]], matrix_b: List[List[int]]) -> List[List[int]]:
34 """
35 Multiply two matrices and return the result modulo MOD.
36
37 Args:
38 matrix_a: First matrix (n x p)
39 matrix_b: Second matrix (p x q)
40
41 Returns:
42 Result matrix (n x q)
43 """
44 rows_a, cols_a, cols_b = len(matrix_a), len(matrix_b), len(matrix_b[0])
45 result = [[0] * cols_b for _ in range(rows_a)]
46
47 for i in range(rows_a):
48 for k in range(cols_a):
49 if matrix_a[i][k]: # Skip if element is 0 for optimization
50 for j in range(cols_b):
51 result[i][j] = (result[i][j] + matrix_a[i][k] * matrix_b[k][j]) % MOD
52
53 return result
54
55 def matrix_power(matrix: List[List[int]], exponent: int) -> List[List[int]]:
56 """
57 Calculate matrix raised to the power of exponent using binary exponentiation.
58
59 Args:
60 matrix: Square matrix to exponentiate
61 exponent: Power to raise the matrix to
62
63 Returns:
64 Matrix raised to the given power
65 """
66 # Initialize result as identity matrix
67 result = [[int(i == j) for j in range(ALPHABET_SIZE)] for i in range(ALPHABET_SIZE)]
68
69 # Binary exponentiation
70 while exponent > 0:
71 if exponent % 2 == 1:
72 result = matrix_multiply(result, matrix)
73 matrix = matrix_multiply(matrix, matrix)
74 exponent //= 2
75
76 return result
77
78 # Convert char_counts to 1xN matrix format for multiplication
79 char_counts_matrix = [char_counts]
80
81 # Calculate transformation matrix raised to power t
82 transformation_factor = matrix_power(transformation_matrix, t)
83
84 # Apply transformations: multiply initial counts by transformation factor
85 final_counts = matrix_multiply(char_counts_matrix, transformation_factor)[0]
86
87 # Sum all character counts to get total length
88 total_length = sum(final_counts) % MOD
89
90 return total_length
91
1class Solution {
2 // Modulo value for preventing integer overflow
3 private final int MOD = (int) 1e9 + 7;
4
5 /**
6 * Calculates the total length of string after t transformations.
7 * Each character can transform into multiple characters based on nums array.
8 *
9 * @param s Initial string
10 * @param t Number of transformations to perform
11 * @param nums List where nums[i] indicates how many characters 'a'+i transforms into
12 * @return Total length of the string after t transformations
13 */
14 public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
15 final int ALPHABET_SIZE = 26;
16
17 // Count frequency of each character in the initial string
18 int[] charCount = new int[ALPHABET_SIZE];
19 for (char c : s.toCharArray()) {
20 charCount[c - 'a']++;
21 }
22
23 // Build transformation matrix where matrix[i][j] = 1 if character i can transform to character j
24 int[][] transformationMatrix = new int[ALPHABET_SIZE][ALPHABET_SIZE];
25 for (int i = 0; i < ALPHABET_SIZE; i++) {
26 int transformCount = nums.get(i);
27 // Character i transforms into the next 'transformCount' characters (with wraparound)
28 for (int j = 1; j <= transformCount; j++) {
29 transformationMatrix[i][(i + j) % ALPHABET_SIZE] = 1;
30 }
31 }
32
33 // Calculate the transformation matrix raised to power t using matrix exponentiation
34 int[][] finalTransformationMatrix = matrixPower(transformationMatrix, t, ALPHABET_SIZE);
35
36 // Multiply initial character count vector with the final transformation matrix
37 int[] resultVector = vectorMatrixMultiply(charCount, finalTransformationMatrix);
38
39 // Sum up all character counts to get the total length
40 int totalLength = 0;
41 for (int count : resultVector) {
42 totalLength = (totalLength + count) % MOD;
43 }
44
45 return totalLength;
46 }
47
48 /**
49 * Multiplies two matrices with modulo operation.
50 *
51 * @param matrixA First matrix (n x p)
52 * @param matrixB Second matrix (p x q)
53 * @return Result matrix (n x q)
54 */
55 private int[][] matmul(int[][] matrixA, int[][] matrixB) {
56 int rows = matrixA.length;
57 int middle = matrixB.length;
58 int cols = matrixB[0].length;
59 int[][] resultMatrix = new int[rows][cols];
60
61 for (int i = 0; i < rows; i++) {
62 for (int k = 0; k < middle; k++) {
63 // Skip multiplication if element is zero for optimization
64 if (matrixA[i][k] == 0) continue;
65
66 for (int j = 0; j < cols; j++) {
67 // Use long to prevent overflow during multiplication
68 resultMatrix[i][j] = (int) ((resultMatrix[i][j] + 1L * matrixA[i][k] * matrixB[k][j]) % MOD);
69 }
70 }
71 }
72
73 return resultMatrix;
74 }
75
76 /**
77 * Calculates matrix raised to a power using binary exponentiation.
78 *
79 * @param matrix Base matrix to be raised to power
80 * @param power Exponent value
81 * @param size Dimension of the square matrix
82 * @return Matrix raised to the given power
83 */
84 private int[][] matpow(int[][] matrix, int power, int size) {
85 // Initialize result as identity matrix
86 int[][] resultMatrix = new int[size][size];
87 for (int i = 0; i < size; i++) {
88 resultMatrix[i][i] = 1;
89 }
90
91 // Binary exponentiation
92 while (power > 0) {
93 // If power is odd, multiply result with current matrix
94 if ((power & 1) != 0) {
95 resultMatrix = matmul(resultMatrix, matrix);
96 }
97 // Square the matrix for next iteration
98 matrix = matmul(matrix, matrix);
99 // Divide power by 2
100 power >>= 1;
101 }
102
103 return resultMatrix;
104 }
105
106 /**
107 * Multiplies a vector with a matrix.
108 *
109 * @param vector Input vector (1 x n)
110 * @param matrix Input matrix (n x n)
111 * @return Result vector (1 x n)
112 */
113 private int[] vectorMatrixMultiply(int[] vector, int[][] matrix) {
114 int dimension = matrix.length;
115 int[] resultVector = new int[dimension];
116
117 for (int i = 0; i < dimension; i++) {
118 long sum = 0;
119 for (int j = 0; j < dimension; j++) {
120 // Multiply vector element with corresponding matrix column
121 sum = (sum + 1L * vector[j] * matrix[j][i]) % MOD;
122 }
123 resultVector[i] = (int) sum;
124 }
125
126 return resultVector;
127 }
128}
129
1class Solution {
2public:
3 // Constants for modulo arithmetic and alphabet size
4 static constexpr int MOD = 1e9 + 7;
5 static constexpr int ALPHABET_SIZE = 26;
6
7 // Type alias for matrix representation
8 using Matrix = vector<vector<int>>;
9
10 /**
11 * Performs matrix multiplication (A * B) with modulo arithmetic
12 * @param matrixA: First matrix (n x p)
13 * @param matrixB: Second matrix (p x q)
14 * @return Result matrix (n x q)
15 */
16 Matrix multiplyMatrices(const Matrix& matrixA, const Matrix& matrixB) {
17 int rowsA = matrixA.size();
18 int colsA = matrixB.size();
19 int colsB = matrixB[0].size();
20
21 Matrix resultMatrix(rowsA, vector<int>(colsB, 0));
22
23 for (int row = 0; row < rowsA; ++row) {
24 for (int k = 0; k < colsA; ++k) {
25 // Skip if element is zero (optimization)
26 if (matrixA[row][k]) {
27 for (int col = 0; col < colsB; ++col) {
28 // Use long long to prevent overflow during multiplication
29 resultMatrix[row][col] = (resultMatrix[row][col] +
30 1LL * matrixA[row][k] * matrixB[k][col] % MOD) % MOD;
31 }
32 }
33 }
34 }
35 return resultMatrix;
36 }
37
38 /**
39 * Computes matrix raised to a power using binary exponentiation
40 * @param baseMatrix: The matrix to be raised to a power
41 * @param exponent: The power to raise the matrix to
42 * @return Result matrix (baseMatrix^exponent)
43 */
44 Matrix matrixPower(Matrix baseMatrix, int exponent) {
45 // Initialize identity matrix as result
46 Matrix identityMatrix(ALPHABET_SIZE, vector<int>(ALPHABET_SIZE, 0));
47 for (int i = 0; i < ALPHABET_SIZE; ++i) {
48 identityMatrix[i][i] = 1;
49 }
50
51 // Binary exponentiation
52 while (exponent > 0) {
53 // If exponent is odd, multiply result with base
54 if (exponent % 2 == 1) {
55 identityMatrix = multiplyMatrices(identityMatrix, baseMatrix);
56 }
57 // Square the base matrix
58 baseMatrix = multiplyMatrices(baseMatrix, baseMatrix);
59 // Halve the exponent
60 exponent /= 2;
61 }
62 return identityMatrix;
63 }
64
65 /**
66 * Calculates the total length of string after t transformations
67 * @param s: Input string
68 * @param t: Number of transformations
69 * @param nums: Array where nums[i] represents how many characters the i-th letter transforms into
70 * @return Total length after transformations modulo MOD
71 */
72 int lengthAfterTransformations(string s, int t, vector<int>& nums) {
73 // Count frequency of each character in the input string
74 vector<int> charFrequency(ALPHABET_SIZE, 0);
75 for (char ch : s) {
76 charFrequency[ch - 'a']++;
77 }
78
79 // Build transformation matrix
80 // transformationMatrix[i][j] = 1 if character i can transform to character j
81 Matrix transformationMatrix(ALPHABET_SIZE, vector<int>(ALPHABET_SIZE, 0));
82 for (int charIndex = 0; charIndex < ALPHABET_SIZE; ++charIndex) {
83 // Each character can transform into the next 'nums[charIndex]' characters (cyclically)
84 for (int offset = 1; offset <= nums[charIndex]; ++offset) {
85 transformationMatrix[charIndex][(charIndex + offset) % ALPHABET_SIZE] = 1;
86 }
87 }
88
89 // Convert character frequency to a 1xN matrix for multiplication
90 Matrix frequencyMatrix(1, vector<int>(ALPHABET_SIZE));
91 for (int i = 0; i < ALPHABET_SIZE; ++i) {
92 frequencyMatrix[0][i] = charFrequency[i];
93 }
94
95 // Compute transformation matrix raised to power t
96 Matrix powerMatrix = matrixPower(transformationMatrix, t);
97
98 // Apply transformations: multiply frequency matrix with power matrix
99 Matrix finalFrequencies = multiplyMatrices(frequencyMatrix, powerMatrix);
100
101 // Sum all character frequencies to get total length
102 int totalLength = 0;
103 for (int frequency : finalFrequencies[0]) {
104 totalLength = (totalLength + frequency) % MOD;
105 }
106
107 return totalLength;
108 }
109};
110
1/**
2 * Calculates the length of string after t transformations
3 * @param s - Initial string
4 * @param t - Number of transformations to apply
5 * @param nums - Array where nums[i] represents how many characters the i-th letter can transform into
6 * @returns The total length after transformations modulo 10^9 + 7
7 */
8function lengthAfterTransformations(s: string, t: number, nums: number[]): number {
9 const MOD: bigint = BigInt(1e9 + 7);
10 const ALPHABET_SIZE: number = 26;
11
12 // Count frequency of each character in the input string
13 const characterCount: number[] = Array(ALPHABET_SIZE).fill(0);
14 for (const char of s) {
15 characterCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
16 }
17
18 // Build transformation matrix where matrix[i][j] represents
19 // whether character i can transform to character j
20 const transformationMatrix: number[][] = Array.from(
21 { length: ALPHABET_SIZE },
22 () => Array(ALPHABET_SIZE).fill(0)
23 );
24
25 for (let i = 0; i < ALPHABET_SIZE; i++) {
26 // Each character can transform into nums[i] subsequent characters
27 for (let j = 1; j <= nums[i]; j++) {
28 transformationMatrix[i][(i + j) % ALPHABET_SIZE] = 1;
29 }
30 }
31
32 // Matrix multiplication function with modulo arithmetic
33 const multiplyMatrices = (matrixA: number[][], matrixB: number[][]): number[][] => {
34 const rowsA: number = matrixA.length;
35 const colsA: number = matrixB.length;
36 const colsB: number = matrixB[0].length;
37 const resultMatrix: number[][] = Array.from(
38 { length: rowsA },
39 () => Array(colsB).fill(0)
40 );
41
42 for (let i = 0; i < rowsA; i++) {
43 for (let k = 0; k < colsA; k++) {
44 const elementA: bigint = BigInt(matrixA[i][k]);
45
46 // Skip multiplication if element is zero
47 if (elementA !== BigInt(0)) {
48 for (let j = 0; j < colsB; j++) {
49 const product: bigint = elementA * BigInt(matrixB[k][j]);
50 const sum: bigint = BigInt(resultMatrix[i][j]) + product;
51 resultMatrix[i][j] = Number(sum % MOD);
52 }
53 }
54 }
55 }
56 return resultMatrix;
57 };
58
59 // Matrix exponentiation using binary exponentiation
60 const matrixPower = (baseMatrix: number[][], exponent: number): number[][] => {
61 // Initialize result as identity matrix
62 let resultMatrix: number[][] = Array.from(
63 { length: ALPHABET_SIZE },
64 (_, i) => Array.from(
65 { length: ALPHABET_SIZE },
66 (_, j) => (i === j ? 1 : 0)
67 )
68 );
69
70 // Binary exponentiation
71 while (exponent > 0) {
72 if (exponent % 2 === 1) {
73 resultMatrix = multiplyMatrices(resultMatrix, baseMatrix);
74 }
75 baseMatrix = multiplyMatrices(baseMatrix, baseMatrix);
76 exponent = Math.floor(exponent / 2);
77 }
78 return resultMatrix;
79 };
80
81 // Convert character count to 1xN matrix for multiplication
82 const countMatrix: number[][] = [characterCount.slice()];
83
84 // Calculate transformation matrix raised to power t
85 const transformationFactor: number[][] = matrixPower(transformationMatrix, t);
86
87 // Apply transformations by multiplying count matrix with transformation factor
88 const finalResult: number[][] = multiplyMatrices(countMatrix, transformationFactor);
89
90 // Sum all character counts in the final result
91 let totalLength: bigint = 0n;
92 for (const count of finalResult[0]) {
93 totalLength = (totalLength + BigInt(count)) % MOD;
94 }
95
96 return Number(totalLength);
97}
98
Time and Space Complexity
Time Complexity: O(n + log t × |Σ|³)
The time complexity breaks down as follows:
O(n)
for counting character frequencies in the initial string, wheren
is the length of strings
- Building the initial transformation matrix takes
O(|Σ|²)
time, where|Σ| = 26
(the alphabet size) - The matrix exponentiation
matpow(matrix, t)
dominates the complexity:- It performs
O(log t)
iterations due to binary exponentiation - Each iteration involves matrix multiplication via
matmul
- Each matrix multiplication of two
|Σ| × |Σ|
matrices takesO(|Σ|³)
time - Total for matrix exponentiation:
O(log t × |Σ|³)
- It performs
- Final matrix multiplication between
cnt
(1 × 26) andfactor
(26 × 26) takesO(|Σ|²)
- Computing the final sum takes
O(|Σ|)
Since |Σ|³ > |Σ|²
and log t × |Σ|³
typically dominates n
for large t
, the overall time complexity is O(n + log t × |Σ|³)
.
Space Complexity: O(|Σ|²)
The space complexity analysis:
cnt
array usesO(|Σ|)
spacematrix
usesO(|Σ|²)
space for the transformation matrixmatmul
creates temporary matrices of sizeO(|Σ|²)
matpow
maintains matrices of sizeO(|Σ|²)
throughout execution- The identity matrix in
matpow
usesO(|Σ|²)
space
The dominant space requirement is O(|Σ|²)
for storing the matrices during computation.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Integer Overflow in Matrix Multiplication
Pitfall: When performing matrix multiplication, the intermediate calculations can exceed integer limits before applying the modulo operation. Even though Python handles arbitrary precision integers, in other languages or when optimizing, developers might forget to apply modulo at each step.
Problem Code:
# Incorrect - might overflow in some languages or cause performance issues res[i][j] = res[i][j] + a[i][k] * b[k][j] res[i][j] %= mod # Modulo applied too late
Solution: Apply modulo operation immediately after each multiplication and addition:
# Correct approach res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod
2. Incorrect Matrix Indexing in Transformation Matrix Construction
Pitfall: The transformation should map character i
to characters (i+1)
through (i+nums[i])
, not starting from i
itself. A common mistake is to include the original character or start from index 0.
Problem Code:
# Incorrect - includes the original character
for j in range(nums[i] + 1): # Should be range(1, nums[i] + 1)
matrix[i][(i + j) % 26] = 1
# Or incorrect - starts from 0 instead of i+1
for j in range(nums[i]):
matrix[i][j] = 1 # Wrong! Should be (i + j + 1) % 26
Solution: Start the range from 1 and add it to the current character index:
# Correct approach
for j in range(1, nums[i] + 1):
matrix[i][(i + j) % 26] = 1
3. Identity Matrix Initialization Error
Pitfall: When initializing the identity matrix for matrix exponentiation, using shallow copy or incorrect initialization can lead to wrong results.
Problem Code:
# Incorrect - creates references to the same list
res = [[0] * 26] * 26
for i in range(26):
res[i][i] = 1 # This modifies multiple rows!
# Or forgetting to set diagonal elements
res = [[0] * 26 for _ in range(26)] # Missing diagonal = 1
Solution: Use list comprehension with proper conditional logic:
# Correct approach
res = [[int(i == j) for j in range(26)] for i in range(26)]
4. Off-by-One Error in Character Frequency Counting
Pitfall: Using incorrect ASCII value calculations when converting characters to indices.
Problem Code:
# Incorrect - might use wrong base
cnt[ord(c) - ord('A')] += 1 # Wrong if lowercase letters
# Or
cnt[ord(c) - 97] += 1 # Magic number, less readable
Solution: Always use ord('a')
for lowercase letters:
# Correct approach
cnt[ord(c) - ord('a')] += 1
5. Forgetting Edge Cases with t = 0
Pitfall: The algorithm should handle t = 0
correctly, returning the original string length without any transformations.
Problem Code:
# Might fail if matrix_power doesn't handle exponent = 0 factor = matrix_power(matrix, t) # What if t = 0?
Solution: The matrix_power function correctly handles this by returning the identity matrix when exponent = 0, which leaves the character counts unchanged. Ensure the while loop condition properly handles zero:
# Correct - returns identity matrix for exponent = 0 while exponent > 0: # Loop doesn't execute when exponent = 0 # ... exponentiation logic return result # Returns identity matrix
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!