Facebook Pixel

2851. String Transformation

HardMathStringDynamic ProgrammingString Matching
Leetcode Link

Problem Description

You have two strings s and t of equal length n. You can perform a specific operation on string s:

Operation: Remove a suffix from s of length l (where 0 < l < n) and append it to the beginning of s. For example, if s = 'abcd', you can remove the suffix 'cd' and place it at the front, resulting in s = 'cdab'.

Given an integer k, you need to find the number of ways to transform string s into string t using exactly k operations.

Since the answer can be very large, return the result modulo 10^9 + 7.

Key Points:

  • Each operation is essentially a rotation of the string
  • You must use exactly k operations (not fewer, not more)
  • The strings s and t have the same length n
  • In each operation, you must remove at least 1 character but not all characters from the end

Example to understand the operation:

  • Starting with s = 'abcd'
  • Remove suffix of length 1: 'd' → Result: 'dabc'
  • Remove suffix of length 2: 'cd' → Result: 'cdab'
  • Remove suffix of length 3: 'bcd' → Result: 'bcda'

The problem asks you to count all possible sequences of k such operations that can transform s into t.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is recognizing that each operation is simply a rotation of the string. When we remove a suffix and prepend it, we're rotating the string. For a string of length n, there are exactly n possible rotations (including the original position).

We can represent each rotation by where the original first character ends up. If the first character of s moves to position i, we can use i as the unique identifier for that rotation state.

First observation: We need to identify which rotations of s match string t. There could be multiple rotations that match (or none at all). To find these efficiently, we can use the Z-algorithm on the concatenated string s + t + t. When we find a substring starting at position i (where n ≤ i < 2n) that matches the prefix of length n, then rotation i - n transforms s into t.

Second observation: This is a path counting problem. We need to count paths of exactly k steps from the initial state (rotation 0) to any target state (rotations that match t).

Third observation: The transition structure is special. From rotation 0, we can reach any of the n-1 non-zero rotations in one step. From any non-zero rotation, we can reach rotation 0 or any of the other n-2 non-zero rotations. This symmetry means all non-zero rotations behave identically!

This leads us to simplify the problem to just two states:

  • State 0: rotation is 0
  • State 1: rotation is non-zero

The transitions become:

  • From state 0: can go to state 1 with n-1 ways
  • From state 1: can go to state 0 with 1 way, or stay in state 1 with n-2 ways

This is now a simple 2-state dynamic programming problem that can be solved with matrix exponentiation for efficiency. We compute dp[k][0] and dp[k][1] using the transition matrix [[0, 1], [n-1, n-2]] raised to the k-th power.

Finally, we sum up the contributions: for each rotation that matches t, we add dp[k][0] if it's rotation 0, or dp[k][1] if it's a non-zero rotation.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution implements several key algorithms and techniques to efficiently solve this problem:

1. Z-Algorithm for Pattern Matching

The getZ method implements the Z-algorithm to find all rotations of s that match t. We concatenate the strings as s + t + t (length 3n) and compute the Z-array:

  • For each position i in range [n, 2n), if z[i] >= n, then rotation (i - n) of s equals t
  • The Z-algorithm efficiently computes the longest prefix match at each position in O(n) time
  • It maintains a window [left, right] representing the rightmost Z-box to avoid redundant comparisons

2. Dynamic Programming with State Reduction

Instead of tracking all n possible rotations, we reduce to 2 states:

  • dp[t][0] = number of ways to reach rotation 0 after exactly t steps
  • dp[t][1] = number of ways to reach any specific non-zero rotation after exactly t steps

The recurrence relations are:

  • dp[t][0] = dp[t-1][1] * (n-1) (from any non-zero rotation, we can reach 0)
  • dp[t][1] = dp[t-1][0] * 1 + dp[t-1][1] * (n-2) (from 0 or from other non-zero rotations)

Initial conditions: dp[0][0] = 1, dp[0][1] = 0

3. Matrix Exponentiation for Fast Computation

To compute dp[k] efficiently for large k, we use matrix multiplication:

[dp[t][0]]   [0      1   ] [dp[t-1][0]]
[dp[t][1]] = [n-1  n-2] * [dp[t-1][1]]

The transition matrix A = [[0, 1], [n-1, n-2]] is raised to the k-th power using fast exponentiation:

  • matrixPower implements binary exponentiation: repeatedly square the matrix and multiply when needed
  • This reduces time complexity from O(k) to O(log k)

4. Modular Arithmetic

All operations use modular arithmetic with MOD = 10^9 + 7:

  • add(x, y): adds two numbers and applies modulo efficiently
  • mul(x, y): multiplies two numbers with modulo
  • These helper functions prevent integer overflow and maintain correctness

5. Final Computation

The numberOfWays method orchestrates the solution:

  1. Compute the transition matrix raised to power k
  2. Extract dp[k][0] and dp[k][1] from the first row
  3. Use Z-algorithm to find all valid target rotations
  4. For each valid rotation r:
    • If r = 0, add dp[k][0] to result
    • If r ≠ 0, add dp[k][1] to result
  5. Return the total count modulo 10^9 + 7

Time Complexity: O(n + log k) - Z-algorithm takes O(n), matrix exponentiation takes O(log k)
Space Complexity: O(n) - for storing the concatenated string and Z-array

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with s = "aba", t = "baa", and k = 2.

Step 1: Identify which rotations of s match t

First, let's see all possible rotations of s = "aba":

  • Rotation 0: "aba" (original)
  • Rotation 1: "aab" (moved 1 char from end to front)
  • Rotation 2: "baa" (moved 2 chars from end to front)

We can see that rotation 2 matches our target t = "baa".

Using the Z-algorithm on s + t + t = "aba" + "baa" + "baa":

  • At position 5 (which is index 2 in the second copy), we find a match of length 3
  • This confirms rotation 5 - 3 = 2 transforms s into t

Step 2: Set up the state transition model

With n = 3, we have:

  • From rotation 0: can reach rotations 1 or 2 (n-1 = 2 ways)
  • From rotation 1: can reach rotations 0 or 2 (move 1 or 2 chars)
  • From rotation 2: can reach rotations 0 or 1 (move 1 or 2 chars)

We simplify to two states:

  • State 0: at rotation 0
  • State 1: at any non-zero rotation (1 or 2)

Step 3: Calculate dp values for k = 2

Initial state: dp[0][0] = 1, dp[0][1] = 0 (we start at rotation 0)

After 1 operation:

  • dp[1][0] = dp[0][1] × 1 = 0 × 1 = 0
  • dp[1][1] = dp[0][0] × 1 + dp[0][1] × (3-2) = 1 × 1 + 0 × 1 = 1

After 2 operations:

  • dp[2][0] = dp[1][1] × 1 = 1 × 1 = 1
  • dp[2][1] = dp[1][0] × 1 + dp[1][1] × (3-2) = 0 × 1 + 1 × 1 = 1

Using matrix form:

[0  1] × [0  1]   [2  1]
[2  1]   [2  1] = [2  3]

First row gives us: dp[2][0] = 2, dp[2][1] = 1

Step 4: Count valid paths

Our target rotation is 2 (non-zero), so we use dp[2][1] = 1.

Result: 1 way

Let's verify by listing all possible 2-operation sequences:

  1. 0 → 1 → 0 (doesn't end at target)
  2. 0 → 1 → 2 ✓ (ends at rotation 2 = "baa")
  3. 0 → 2 → 0 (doesn't end at target)
  4. 0 → 2 → 1 (doesn't end at target)

Indeed, there's exactly 1 way to reach t = "baa" in exactly 2 operations.

Consider s = "aa", t = "aa", k = 1.

Step 1: Identify matching rotations

  • Rotation 0: "aa" ✓
  • Rotation 1: "aa" ✓

Both rotations match t!

Step 2: Calculate dp values for k = 1

  • dp[1][0] = 0 (can't return to rotation 0 in 1 step)
  • dp[1][1] = 1 (can reach rotation 1 from rotation 0)

Step 3: Count valid paths

  • Rotation 0 contributes: dp[1][0] = 0
  • Rotation 1 contributes: dp[1][1] = 1

Result: 0 + 1 = 1 way

This shows how the algorithm handles cases where multiple rotations of s equal t.

Solution Implementation

1class Solution:
2    MOD: int = 1000000007
3
4    def add(self, x: int, y: int) -> int:
5        """Add two numbers with modulo operation."""
6        x += y
7        if x >= self.MOD:
8            x -= self.MOD
9        return x
10
11    def mul(self, x: int, y: int) -> int:
12        """Multiply two numbers with modulo operation."""
13        return (x * y) % self.MOD
14
15    def getZ(self, s: str) -> List[int]:
16        """
17        Compute Z-array using Z-algorithm.
18        Z[i] represents the length of the longest substring starting from s[i] 
19        which is also a prefix of s.
20        """
21        n = len(s)
22        z_array = [0] * n
23        left = right = 0
24      
25        for i in range(1, n):
26            # If i is within the Z-box, we can use previously computed values
27            if i <= right and z_array[i - left] <= right - i:
28                z_array[i] = z_array[i - left]
29            else:
30                # Calculate Z[i] from scratch or extend beyond the Z-box
31                z_value = max(0, right - i + 1)
32                while i + z_value < n and s[i + z_value] == s[z_value]:
33                    z_value += 1
34                z_array[i] = z_value
35          
36            # Update the Z-box if we've found a longer match
37            if i + z_array[i] - 1 > right:
38                left = i
39                right = i + z_array[i] - 1
40              
41        return z_array
42
43    def matrixMultiply(self, matrix_a: List[List[int]], matrix_b: List[List[int]]) -> List[List[int]]:
44        """
45        Multiply two matrices with modulo operation.
46        matrix_a is m x n, matrix_b is n x p, result is m x p.
47        """
48        rows_a = len(matrix_a)
49        cols_a = len(matrix_a[0])
50        cols_b = len(matrix_b[0])
51      
52        # Initialize result matrix with zeros
53        result = [[0] * cols_b for _ in range(rows_a)]
54      
55        # Perform matrix multiplication
56        for i in range(rows_a):
57            for j in range(cols_b):
58                for k in range(cols_a):
59                    result[i][j] = self.add(result[i][j], 
60                                           self.mul(matrix_a[i][k], matrix_b[k][j]))
61        return result
62
63    def matrixPower(self, matrix: List[List[int]], exponent: int) -> List[List[int]]:
64        """
65        Calculate matrix raised to the power of exponent using fast exponentiation.
66        """
67        size = len(matrix)
68      
69        # Initialize result as identity matrix
70        result = [[0] * size for _ in range(size)]
71        for i in range(size):
72            result[i][i] = 1
73      
74        # Create a copy of the input matrix for manipulation
75        base = [row[:] for row in matrix]
76      
77        # Fast exponentiation
78        while exponent > 0:
79            if exponent & 1:  # If exponent is odd
80                result = self.matrixMultiply(result, base)
81            base = self.matrixMultiply(base, base)
82            exponent >>= 1  # Divide exponent by 2
83          
84        return result
85
86    def numberOfWays(self, s: str, t: str, k: int) -> int:
87        """
88        Count the number of ways to transform string s to string t in exactly k operations.
89        Each operation rotates the string by moving some prefix to the end.
90        """
91        n = len(s)
92      
93        # Calculate dp values using matrix exponentiation
94        # dp[0] = ways to reach position 0 (original string)
95        # dp[1] = ways to reach any non-zero position
96        transition_matrix = [[0, 1], [n - 1, n - 2]]
97        power_matrix = self.matrixPower(transition_matrix, k)
98        dp_values = power_matrix[0]  # First row gives us [dp[k][0], dp[k][1]]
99      
100        # Concatenate strings for Z-algorithm: s + t + t
101        concatenated = s + t + t
102        z_array = self.getZ(concatenated)
103      
104        # Check all possible rotations of t that match s
105        result = 0
106        double_n = n + n
107      
108        for i in range(n, double_n):
109            # If the substring starting at position i matches at least n characters,
110            # it means rotating s by (i - n) positions gives us t
111            if z_array[i] >= n:
112                rotation_amount = i - n
113                # Add the number of ways to achieve this rotation in k steps
114                if rotation_amount == 0:
115                    result = self.add(result, dp_values[0])
116                else:
117                    result = self.add(result, dp_values[1])
118                  
119        return result
120
1class Solution {
2    // Modulo constant for preventing integer overflow
3    private static final int MOD = 1000000007;
4
5    /**
6     * Adds two numbers under modulo operation
7     * @param x first number
8     * @param y second number
9     * @return (x + y) % MOD
10     */
11    private int add(int x, int y) {
12        x += y;
13        if (x >= MOD) {
14            x -= MOD;
15        }
16        return x;
17    }
18
19    /**
20     * Multiplies two numbers under modulo operation
21     * @param x first number
22     * @param y second number
23     * @return (x * y) % MOD
24     */
25    private int mul(long x, long y) {
26        return (int) (x * y % MOD);
27    }
28
29    /**
30     * Computes Z-array for string matching
31     * Z[i] represents the length of the longest substring starting from i
32     * which is also a prefix of the string
33     * @param s input string
34     * @return Z-array
35     */
36    private int[] getZ(String s) {
37        int n = s.length();
38        int[] zArray = new int[n];
39      
40        // left and right maintain the window [left, right] which matches with prefix
41        for (int i = 1, left = 0, right = 0; i < n; ++i) {
42            // Case 1: i is within the current Z-box
43            if (i <= right && zArray[i - left] <= right - i) {
44                zArray[i] = zArray[i - left];
45            } else {
46                // Case 2: i is outside the current Z-box or needs extension
47                int zValue = Math.max(0, right - i + 1);
48              
49                // Extend the match as far as possible
50                while (i + zValue < n && s.charAt(i + zValue) == s.charAt(zValue)) {
51                    zValue++;
52                }
53                zArray[i] = zValue;
54            }
55          
56            // Update the Z-box if we found a longer match
57            if (i + zArray[i] - 1 > right) {
58                left = i;
59                right = i + zArray[i] - 1;
60            }
61        }
62        return zArray;
63    }
64
65    /**
66     * Multiplies two matrices with modulo operation
67     * @param matrixA first matrix
68     * @param matrixB second matrix
69     * @return result of matrixA * matrixB
70     */
71    private int[][] matrixMultiply(int[][] matrixA, int[][] matrixB) {
72        int rows = matrixA.length;
73        int cols = matrixA[0].length;
74        int resultCols = matrixB[0].length;
75        int[][] result = new int[rows][resultCols];
76      
77        // Standard matrix multiplication with modulo
78        for (int i = 0; i < rows; ++i) {
79            for (int j = 0; j < resultCols; ++j) {
80                for (int k = 0; k < cols; ++k) {
81                    result[i][j] = add(result[i][j], mul(matrixA[i][k], matrixB[k][j]));
82                }
83            }
84        }
85        return result;
86    }
87
88    /**
89     * Computes matrix power using binary exponentiation
90     * @param matrix base matrix
91     * @param exponent power to raise the matrix to
92     * @return matrix^exponent
93     */
94    private int[][] matrixPower(int[][] matrix, long exponent) {
95        int size = matrix.length;
96      
97        // Initialize result as identity matrix
98        int[][] result = new int[size][size];
99        for (int i = 0; i < size; ++i) {
100            result[i][i] = 1;
101        }
102      
103        // Create a copy of the input matrix for manipulation
104        int[][] base = new int[size][size];
105        for (int i = 0; i < size; ++i) {
106            System.arraycopy(matrix[i], 0, base[i], 0, size);
107        }
108      
109        // Binary exponentiation
110        while (exponent > 0) {
111            if ((exponent & 1) == 1) {
112                result = matrixMultiply(result, base);
113            }
114            base = matrixMultiply(base, base);
115            exponent >>= 1;
116        }
117        return result;
118    }
119
120    /**
121     * Counts the number of ways to transform string s to string t in exactly k operations
122     * Each operation is a cyclic shift of the string
123     * @param s source string
124     * @param t target string
125     * @param k number of operations
126     * @return number of ways modulo MOD
127     */
128    public int numberOfWays(String s, String t, long k) {
129        int n = s.length();
130      
131        // Dynamic programming transition matrix for cyclic shifts
132        // dp[0] represents ways when shift is 0 (same position)
133        // dp[1] represents ways when shift is non-zero
134        int[] dp = matrixPower(new int[][] {{0, 1}, {n - 1, n - 2}}, k)[0];
135      
136        // Concatenate strings for pattern matching
137        String combined = s + t + t;
138      
139        // Find all positions where t can be obtained from cyclic shifts of s
140        int[] zArray = getZ(combined);
141      
142        int totalLength = n + n;
143        int result = 0;
144      
145        // Check each possible starting position in the concatenated string
146        for (int i = n; i < totalLength; ++i) {
147            // If match length >= n, then t can be obtained from this cyclic shift
148            if (zArray[i] >= n) {
149                // Add corresponding dp value based on shift amount
150                int shift = i - n;
151                result = add(result, dp[shift == 0 ? 0 : 1]);
152            }
153        }
154      
155        return result;
156    }
157}
158
1class Solution {
2private:
3    const int MOD = 1000000007;
4
5    // Add two numbers with modulo operation
6    int addMod(int x, int y) {
7        x += y;
8        if (x >= MOD) {
9            x -= MOD;
10        }
11        return x;
12    }
13
14    // Multiply two numbers with modulo operation
15    int multiplyMod(long long x, long long y) {
16        return (x * y) % MOD;
17    }
18
19    // Compute Z-array using Z-algorithm
20    // Z[i] represents the length of the longest substring starting from s[i] 
21    // which is also a prefix of s
22    vector<int> computeZArray(const string& str) {
23        const int n = str.length();
24        vector<int> zArray(n);
25      
26        // left and right maintain the window [left, right] which matches with prefix
27        int left = 0, right = 0;
28      
29        for (int i = 1; i < n; ++i) {
30            // Case 1: i is within the current Z-box
31            if (i <= right && zArray[i - left] <= right - i) {
32                zArray[i] = zArray[i - left];
33            } 
34            // Case 2: i is outside the current Z-box or needs extension
35            else {
36                // Start matching from position i (or continue from right - i + 1)
37                zArray[i] = max(0, right - i + 1);
38                while (i + zArray[i] < n && str[i + zArray[i]] == str[zArray[i]]) {
39                    zArray[i]++;
40                }
41            }
42          
43            // Update the Z-box if we found a longer match
44            if (i + zArray[i] - 1 > right) {
45                left = i;
46                right = i + zArray[i] - 1;
47            }
48        }
49      
50        return zArray;
51    }
52
53    // Matrix multiplication with modulo operation
54    vector<vector<int>> matrixMultiply(const vector<vector<int>>& matrixA, 
55                                       const vector<vector<int>>& matrixB) {
56        const int rows = matrixA.size();
57        const int cols = matrixA[0].size();
58        const int resultCols = matrixB[0].size();
59      
60        vector<vector<int>> result(rows, vector<int>(resultCols, 0));
61      
62        for (int i = 0; i < rows; ++i) {
63            for (int j = 0; j < cols; ++j) {
64                for (int k = 0; k < resultCols; ++k) {
65                    result[i][k] = addMod(result[i][k], 
66                                         multiplyMod(matrixA[i][j], matrixB[j][k]));
67                }
68            }
69        }
70      
71        return result;
72    }
73
74    // Matrix exponentiation using binary exponentiation
75    vector<vector<int>> matrixPower(const vector<vector<int>>& matrix, long long exponent) {
76        const int size = matrix.size();
77      
78        // Initialize result as identity matrix
79        vector<vector<int>> result(size, vector<int>(size, 0));
80        for (int i = 0; i < size; ++i) {
81            result[i][i] = 1;
82        }
83      
84        // Copy input matrix for manipulation
85        auto base = matrix;
86      
87        // Binary exponentiation
88        while (exponent > 0) {
89            if (exponent & 1) {
90                result = matrixMultiply(result, base);
91            }
92            base = matrixMultiply(base, base);
93            exponent >>= 1;
94        }
95      
96        return result;
97    }
98
99public:
100    int numberOfWays(string s, string t, long long k) {
101        const int n = s.length();
102      
103        // Create transition matrix for the problem
104        // dp[0] represents ways when rotation index is 0 (same position)
105        // dp[1] represents ways when rotation index is not 0 (different position)
106        const auto dpMatrix = matrixPower({{0, 1}, {n - 1, n - 2}}, k)[0];
107      
108        // Concatenate strings for Z-algorithm application
109        // Pattern: s + t + t to find all cyclic matches
110        string concatenated = s + t + t;
111      
112        // Compute Z-array for pattern matching
113        const auto zArray = computeZArray(concatenated);
114      
115        const int totalLength = n + n;
116        int result = 0;
117      
118        // Check each position in the second copy of t
119        for (int i = n; i < totalLength; ++i) {
120            // If we have a full match (Z-value >= n), it means s can be rotated to match t
121            if (zArray[i] >= n) {
122                // Add the number of ways based on whether this is rotation by 0 or not
123                // i - n gives the rotation amount
124                int rotationAmount = i - n;
125                result = addMod(result, dpMatrix[rotationAmount != 0 ? 1 : 0]);
126            }
127        }
128      
129        return result;
130    }
131};
132
1const MOD = 1000000007;
2
3// Add two numbers with modulo operation
4function addMod(x: number, y: number): number {
5    x += y;
6    if (x >= MOD) {
7        x -= MOD;
8    }
9    return x;
10}
11
12// Multiply two numbers with modulo operation
13function multiplyMod(x: number, y: number): number {
14    return (x * y) % MOD;
15}
16
17// Compute Z-array using Z-algorithm
18// Z[i] represents the length of the longest substring starting from str[i] 
19// which is also a prefix of str
20function computeZArray(str: string): number[] {
21    const n = str.length;
22    const zArray: number[] = new Array(n).fill(0);
23  
24    // left and right maintain the window [left, right] which matches with prefix
25    let left = 0;
26    let right = 0;
27  
28    for (let i = 1; i < n; i++) {
29        // Case 1: i is within the current Z-box
30        if (i <= right && zArray[i - left] <= right - i) {
31            zArray[i] = zArray[i - left];
32        } 
33        // Case 2: i is outside the current Z-box or needs extension
34        else {
35            // Start matching from position i (or continue from right - i + 1)
36            zArray[i] = Math.max(0, right - i + 1);
37            while (i + zArray[i] < n && str[i + zArray[i]] === str[zArray[i]]) {
38                zArray[i]++;
39            }
40        }
41      
42        // Update the Z-box if we found a longer match
43        if (i + zArray[i] - 1 > right) {
44            left = i;
45            right = i + zArray[i] - 1;
46        }
47    }
48  
49    return zArray;
50}
51
52// Matrix multiplication with modulo operation
53function matrixMultiply(matrixA: number[][], matrixB: number[][]): number[][] {
54    const rows = matrixA.length;
55    const cols = matrixA[0].length;
56    const resultCols = matrixB[0].length;
57  
58    const result: number[][] = Array(rows).fill(null).map(() => Array(resultCols).fill(0));
59  
60    for (let i = 0; i < rows; i++) {
61        for (let j = 0; j < cols; j++) {
62            for (let k = 0; k < resultCols; k++) {
63                result[i][k] = addMod(result[i][k], 
64                                     multiplyMod(matrixA[i][j], matrixB[j][k]));
65            }
66        }
67    }
68  
69    return result;
70}
71
72// Matrix exponentiation using binary exponentiation
73function matrixPower(matrix: number[][], exponent: number): number[][] {
74    const size = matrix.length;
75  
76    // Initialize result as identity matrix
77    const result: number[][] = Array(size).fill(null).map(() => Array(size).fill(0));
78    for (let i = 0; i < size; i++) {
79        result[i][i] = 1;
80    }
81  
82    // Copy input matrix for manipulation
83    let base = matrix.map(row => [...row]);
84  
85    // Binary exponentiation
86    let exp = exponent;
87    while (exp > 0) {
88        if (exp & 1) {
89            const temp = matrixMultiply(result, base);
90            for (let i = 0; i < size; i++) {
91                for (let j = 0; j < size; j++) {
92                    result[i][j] = temp[i][j];
93                }
94            }
95        }
96        base = matrixMultiply(base, base);
97        exp = Math.floor(exp / 2);
98    }
99  
100    return result;
101}
102
103function numberOfWays(s: string, t: string, k: number): number {
104    const n = s.length;
105  
106    // Create transition matrix for the problem
107    // dp[0] represents ways when rotation index is 0 (same position)
108    // dp[1] represents ways when rotation index is not 0 (different position)
109    const dpMatrix = matrixPower([[0, 1], [n - 1, n - 2]], k)[0];
110  
111    // Concatenate strings for Z-algorithm application
112    // Pattern: s + t + t to find all cyclic matches
113    const concatenated = s + t + t;
114  
115    // Compute Z-array for pattern matching
116    const zArray = computeZArray(concatenated);
117  
118    const totalLength = n + n;
119    let result = 0;
120  
121    // Check each position in the second copy of t
122    for (let i = n; i < totalLength; i++) {
123        // If we have a full match (Z-value >= n), it means s can be rotated to match t
124        if (zArray[i] >= n) {
125            // Add the number of ways based on whether this is rotation by 0 or not
126            // i - n gives the rotation amount
127            const rotationAmount = i - n;
128            result = addMod(result, dpMatrix[rotationAmount !== 0 ? 1 : 0]);
129        }
130    }
131  
132    return result;
133}
134

Time and Space Complexity

Time Complexity: O(n + log k)

The time complexity breaks down into several components:

  1. Z-algorithm (getZ function): O(n) where n is the length of the concatenated string s + t + t (which is 3n). The Z-algorithm processes each character at most twice (once when extending right, once when using previously computed values), resulting in linear time complexity.

  2. Matrix Power (matrixPower function): O(log k) for computing the k-th power of a 2×2 matrix using fast exponentiation. Since the matrix is fixed size (2×2), each matrix multiplication takes O(1) time, and we perform O(log k) multiplications due to the binary exponentiation approach.

  3. Matrix Multiplication (matrixMultiply function): For 2×2 matrices, this is O(1) per multiplication.

  4. Final loop to calculate result: O(n) to iterate through positions from n to 2n and check Z-values.

Overall: O(3n) + O(log k) + O(n) = O(n + log k)

Space Complexity: O(n)

The space complexity consists of:

  1. Concatenated string: O(3n) = O(n) for storing s + t + t

  2. Z-array: O(3n) = O(n) for storing the Z-values

  3. Matrix operations: O(1) since we're working with fixed 2×2 matrices

  4. Other variables: O(1) for counters, indices, and the result

Overall: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Understanding of Valid Rotations

Pitfall: A common mistake is assuming that we need to check if rotating s by some amount gives us t, when actually we need to check if rotating t gives us s. This confusion arises because the operation moves a suffix of the current string to the front.

Why it happens: The problem states we transform s into t, so intuitively we think about rotating s. However, after k operations starting from s, we need to end up at t. The Z-algorithm checks which rotations of s equal t.

Solution: The code correctly handles this by concatenating s + t + t and checking positions in range [n, 2n). If z[i] >= n for position i, it means the rotation of s by (i - n) positions equals t.

2. Off-by-One Error in Rotation Count

Pitfall: Miscounting the number of valid rotations, especially forgetting that rotation by 0 (identity) and rotation by n (full rotation) are different cases.

Example: For s = "abc", there are exactly 3 unique rotations:

  • Rotation by 0: "abc" (identity)
  • Rotation by 1: "cab"
  • Rotation by 2: "bca"

Solution: The code correctly handles this by:

  • Treating rotation 0 separately with dp[k][0]
  • Having exactly n-1 non-zero rotations, each tracked by dp[k][1]
  • The transition matrix correctly uses n-1 and n-2 for the coefficients

3. Integer Overflow in Matrix Multiplication

Pitfall: When multiplying large numbers in the matrix operations, intermediate results can overflow even before applying modulo, leading to incorrect results.

# Incorrect - can overflow
result[i][j] = (result[i][j] + matrix_a[i][k] * matrix_b[k][j]) % MOD

# Correct - uses helper functions
result[i][j] = self.add(result[i][j], self.mul(matrix_a[i][k], matrix_b[k][j]))

Solution: The code uses dedicated add() and mul() helper functions that handle modulo arithmetic safely, preventing overflow at each step.

4. Inefficient DP State Representation

Pitfall: Tracking all n possible rotation states individually, leading to:

  • Space complexity of O(n × k) for the DP table
  • Time complexity of O(n² × k) for computation

Why it's tempting: It seems natural to track dp[step][rotation] for each possible rotation.

Solution: The code brilliantly reduces states to just 2:

  • State 0: at original position
  • State 1: at any non-zero rotation position

This optimization is valid because all non-zero rotations have symmetric transition probabilities, reducing complexity dramatically.

5. Misunderstanding the Operation Constraint

Pitfall: Forgetting that each operation must move at least 1 character but not all n characters. Some might incorrectly allow:

  • Moving 0 characters (no operation)
  • Moving all n characters (returns to original position)

Solution: The code enforces this by having exactly n-1 valid operations from any position, as seen in the transition matrix. From position 0, we can reach any of the n-1 non-zero positions. From any non-zero position, we can reach 0 or any of the other n-2 non-zero positions.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Recommended Readings

Math Basics

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

Dynamic Programming Introduction and Patterns

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: The Smart, Data-Driven Way to Prepare for Tech Interviews

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!

Load More