2851. String Transformation
Problem Description
You are tasked with transforming one string, s, into another string, t, both of equal length n. The allowed transformation is to choose a non-empty suffix from s and move it to the front of the string. For example, if s is 'abcd', you can take the suffix 'cd' and rearrange s to become 'cdab'. You have a specific number of operations, k, to perform this transformation. Your goal is to determine the number of ways to exactly transform s into t using precisely k operations. The result should be given modulo 10^9 + 7.
Intuition
The solution to this problem leverages dynamic programming (DP), the Z-algorithm for string matching, and fast modular exponentiation to efficiently compute the desired output.
-
String Representation: Since each operation is essentially a rotation of the string
s, you can represent the resulting string using an integer from0ton - 1, indicating the new index of the original first character ofs. -
Target String Representation: By concatenating
s + t + t, and using the Z-algorithm, you can find all valid rotations ofsthat matcht. A rotation is valid if a substring starting at an index in[n, 2n)is a prefix match totthat covers the entire length oft. -
Dynamic Programming: The DP equation considers two states:
dp[t][0]is the number of ways to return to the original string aftertoperations.dp[t][1]is the number of ways to have a non-original string aftertoperations.
-
State Transition: The transitions are:
- From a non-original to the original string, it's always possible with
n - 1ways (because any non-original string can contribute to the original string in one operation). - From an original to a non-original or amongst non-original strings, there are
n - 2ways (since you can't pick the suffix that transforms the string to itself).
- From a non-original to the original string, it's always possible with
-
Matrix Multiplication: To optimize the calculation of
dp[k], the solution uses matrix multiplication, expressing the transition as a matrix and then raising this matrix to the powerk, which can be done efficiently using the "fast power" algorithm.
The DP base cases are dp[0][0] = 1 (the original string is already s without any operations), and dp[0][1] = 0 (no ways to have a non-original string without operations).
Finally, apply the calculated transition rules by raising the transition matrix to the power k, use the Z-algorithm results to identify which rotations can form t, and sum up the number of ways each valid rotation can be reached in k operations.
Learn more about Math and Dynamic Programming patterns.
Which of the following array represent a max heap?
Solution Approach
The solution's implementation can be outlined in the following steps:
-
String Representation & Z-algorithm:
- Concatenate
s,t, andtagain to create a new string on which Z-algorithm is applied. This algorithm runs inO(n)time and creates a Z-arrayzwherez[i]represents the length of the longest substring starting fromithat matches the prefix of the string. - A valid rotation of
sthat can matchtis identified if there's a prefix match of lengthnstarting at positions in the range[n, 2n)in the concatenated string.
- Concatenate
-
Dynamic Programming Set-up:
- Define DP states
dp[t][0]anddp[t][1]wheretis the number of operations and the second index indicates whether the string is the original (0) or a rotation (1).
- Define DP states
-
State Transitions:
- Calculated as
dp[t][0] = dp[t - 1][1] * (n - 1)for returning to the original string. - Calculated as
dp[t][1] = dp[t - 1][0] + dp[t - 1][1] * (n - 2)for all the non-zero strings which can be reached from a zero string or from any other non-zero string.
- Calculated as
-
Matrix Multiplication:
- To compute
dp[k][x]quickly, the state transition equations are represented as a matrix[ [0, 1], [n - 1, n - 2] ], which is then multiplied with the vector(dp[t-1][0], dp[t-1][1]). - The matrix power is computed using the "fast power" algorithm which efficiently computes large power by repeatedly squaring the matrix and multiplying when the current power is odd.
- To compute
-
The Matrix Power Function:
- This function repeatedly squares the matrix for
log(k)times to compute high powers. - It multiplies the current matrix when the bit is set in the binary representation of
k.
- This function repeatedly squares the matrix for
-
Considering Valid Rotations:
- After calculating
dp = matrixPower([[0, 1], [n - 1, n - 2]], k)[0], iterate for each indexiin[n, 2n)and ifz[i]indicates a valid rotation, accumulatedp[0]if it is an original string (i - n == 0) ordp[1]otherwise.
- After calculating
-
Final Result:
- Since we're interested in finding the number of ways modulo
10^9 + 7, all additions and multiplications are done moduloM.
- Since we're interested in finding the number of ways modulo
By using these techniques, the solution avoids brute force computation which would be infeasible for large n and k, keeping the time complexity down to O(n + logk) and space complexity to O(n).
How many ways can you arrange the three letters A, B and C?
Example Walkthrough
Let's take a small example to illustrate the solution approach:
- Let
s = "ab",t = "ba", andk = 2.
We need to determine the number of ways to transform s into t using exactly k operations.
-
String Representation & Z-algorithm:
- We concatenate
s + t + twhich gives"abbaab". - Applying the Z-algorithm on this string, we get the Z-array:
z = [0, 0, 1, 2, 1, 0]. What matters are elementsz[2] = 1andz[3] = 2. - We see that
z[3] = 2implies there is a rotation, by moving the suffix"ab"to the front, that matchest.
- We concatenate
-
Dynamic Programming Set-up:
- We define a 2D DP array where
dp[i][0]is the number of ways to have the original string afterioperations, anddp[i][1]is for the non-original strings.
- We define a 2D DP array where
-
State Transitions:
- We establish the transitions
dp[t][0] = dp[t - 1][1] * 1(sincen - 1 = 2 - 1 = 1here) anddp[t][1] = dp[t - 1][0] + dp[t - 1][1] * 0.
- We establish the transitions
-
Matrix Multiplication:
- The transition matrix for our example is
[ [0, 1], [1, 0] ]sincen = 2. - We need to calculate the matrix raised to the power of
k, which is2.
- The transition matrix for our example is
-
The Matrix Power Function:
- The function used to raise our matrix to the power of
kwill essentially computematrix^2. - After the computation, we get that the raised matrix is still
[ [0, 1], [1, 0] ].
- The function used to raise our matrix to the power of
-
Considering Valid Rotations:
- We now calculate
dp = matrixPower([[0, 1], [1, 0]], 2)[0], which gives us[1, 0]as there is one way to get the original string"ab"in 2 operations, which is doing nothing twice.
- We now calculate
-
Final Result:
- We iterate over the considered range, and see
z[3]indicates a valid rotation. - Since it is not a rotation to the original string (
3 - n != 0), we considerdp[1], but sincedp[1] = 0, there are no valid ways for this example. - The final result is
0modulo10^9 + 7.
- We iterate over the considered range, and see
Through this walkthrough with a simple example, we demonstrated how the solution method applies the specific steps of string manipulation, dynamic programming, matrix exponentiation, and the z-algorithm to compute the number of ways to transform one string to another given a specific number of operations.
Solution Implementation
1from typing import List
2
3MOD = 1000000007 # Prime modulus used for preventing integer overflow
4
5class Solution:
6 def add(self, x: int, y: int) -> int:
7 """Helper function to perform addition under modulus."""
8 return (x + y) % MOD
9
10 def mul(self, x: int, y: int) -> int:
11 """Helper function to perform multiplication under modulus."""
12 return (x * y) % MOD
13
14 def get_z_array(self, s: str) -> List[int]:
15 """
16 Implementation of Z algorithm.
17
18 For a string 's', z_array is an array where each z_array[i] is equal
19 to the greatest number of characters starting from the string index i
20 that coincide with the first characters of s.
21 """
22 n = len(s)
23 z_array = [0] * n
24 l, r = 0, 0
25 for i in range(1, n):
26 if i <= r:
27 z_array[i] = min(r - i + 1, z_array[i - l])
28 while i + z_array[i] < n and s[z_array[i]] == s[i + z_array[i]]:
29 z_array[i] += 1
30 if i + z_array[i] - 1 > r:
31 l, r = i, i + z_array[i] - 1
32 return z_array
33
34 def matrix_multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
35 """Multiplication of two matrices under modulus."""
36 m, n, p = len(a), len(a[0]), len(b[0])
37 result = [[0] * p for _ in range(m)]
38 for i in range(m):
39 for j in range(p):
40 for k in range(n):
41 result[i][j] = self.add(result[i][j], self.mul(a[i][k], b[k][j]))
42 return result
43
44 def matrix_power(self, a: List[List[int]], k: int) -> List[List[int]]:
45 """Exponentiation of matrix 'a' to the power 'k' under modulus."""
46 n = len(a)
47 result = [[int(i == j) for j in range(n)] for i in range(n)] # identity matrix
48 while k > 0:
49 if k & 1:
50 result = self.matrix_multiply(result, a)
51 a = self.matrix_multiply(a, a)
52 k >>= 1
53 return result
54
55 def number_of_ways(self, s: str, t: str, k: int) -> int:
56 """Calculate the number of ways to form string 't' from string 's' with 'k' operations."""
57 n = len(s)
58 initial_dp = [[0, 1], [n - 1, n - 2]]
59 dp = self.matrix_power(initial_dp, k)[0]
60 extended_s = s + t + t
61 z = self.get_z_array(extended_s)
62 result = 0
63 for i in range(n, 2 * n):
64 if z[i] >= n:
65 result = self.add(result, dp[1] if (i - n) else dp[0])
66 return result
671class Solution {
2 private static final int MOD = 1000000007; // Define the modulus value for operations to prevent overflow
3
4 // Method to perform addition modulo MOD
5 private int add(int x, int y) {
6 x += y; // Add y to x
7 if (x >= MOD) { // If the result is greater than MOD, subtract MOD from it
8 x -= MOD;
9 }
10 return x; // Return the result after modulo
11 }
12
13 // Method to perform multiplication modulo MOD
14 private int mul(long x, long y) {
15 return (int) ((x * y) % MOD); // Multiply x and y, then take the result modulo MOD
16 }
17
18 // Method to compute the Z-array of a string
19 private int[] getZ(String str) {
20 int length = str.length();
21 int[] z = new int[length];
22 for (int i = 1, left = 0, right = 0; i < length; ++i) {
23 if (i <= right && z[i - left] <= right - i) {
24 z[i] = z[i - left];
25 } else {
26 int z_i = Math.max(0, right - i + 1);
27 while (i + z_i < length && str.charAt(i + z_i) == str.charAt(z_i)) {
28 z_i++;
29 }
30 z[i] = z_i;
31 }
32 if (i + z[i] - 1 > right) {
33 left = i;
34 right = i + z[i] - 1;
35 }
36 }
37 return z; // Return the Z-array
38 }
39
40 // Method to multiply two matrices
41 private int[][] matrixMultiply(int[][] a, int[][] b) {
42 int rows = a.length, cols = a[0].length, inner = b[0].length;
43 int[][] result = new int[rows][inner];
44 for (int i = 0; i < rows; ++i) {
45 for (int j = 0; j < inner; ++j) {
46 for (int k = 0; k < cols; ++k) {
47 result[i][j] = add(result[i][j], mul(a[i][k], b[k][j]));
48 }
49 }
50 }
51 return result; // Return the product of the matrices
52 }
53
54 // Method for exponentiating a matrix by a power y
55 // It uses the square-and-multiply technique.
56 private int[][] matrixPower(int[][] matrix, long power) {
57 int size = matrix.length;
58 int[][] result = new int[size][size];
59 for (int i = 0; i < size; ++i) {
60 result[i][i] = 1;
61 }
62 int[][] tempMatrix = new int[size][size];
63 for (int i = 0; i < size; ++i) {
64 System.arraycopy(matrix[i], 0, tempMatrix[i], 0, size);
65 }
66 while (power > 0) {
67 if ((power & 1) == 1) {
68 result = matrixMultiply(result, tempMatrix);
69 }
70 tempMatrix = matrixMultiply(tempMatrix, tempMatrix);
71 power >>= 1;
72 }
73 return result; // Return the matrix raised to power 'power'
74 }
75
76 // Method to calculate the number of ways the sequence t can be inserted into s after 'k' steps
77 public int numberOfWays(String s, String t, long k) {
78 int strLength = s.length();
79 // Calculate matrix power with base matrix and exponent k
80 int[] dp = matrixPower(new int[][] {{0, 1}, {strLength - 1, strLength - 2}}, k)[0];
81 s += t + t; // Concatenate the strings
82 int[] z = getZ(s); // Get the Z-array
83 int result = 0;
84 for (int i = strLength; i < 2 * strLength; ++i) {
85 if (z[i] >= strLength) { // If Z-value is greater or equal to length of s, it's a match
86 result = add(result, dp[i - strLength == 0 ? 0 : 1]); // Update result accordingly
87 }
88 }
89 return result; // Return the final result
90 }
91}
921#include <vector>
2#include <string>
3using std::vector;
4using std::string;
5using std::max;
6
7class Solution {
8 // Define modulo constant for operations to ensure result remains within integer bounds.
9 static const int MOD = 1e9 + 7;
10
11 // Utility function to perform addition under modulo.
12 int add(int x, int y) {
13 x += y;
14 if (x >= MOD) {
15 x -= MOD;
16 }
17 return x;
18 }
19
20 // Utility function to perform multiplication under modulo.
21 int mul(long long x, long long y) {
22 return static_cast<int>((x * y) % MOD);
23 }
24
25 // Generate Z-array for string matching, which will be used to find the number of matches of t in s.
26 vector<int> generateZArray(const string& s) {
27 const int n = s.length();
28 vector<int> z(n);
29 for (int i = 1, left = 0, right = 0; i < n; ++i) {
30 if (i <= right && z[i - left] < right - i + 1) {
31 z[i] = z[i - left];
32 } else {
33 z[i] = max(0, right - i + 1);
34 while (i + z[i] < n && s[i + z[i]] == s[z[i]]) {
35 ++z[i];
36 }
37 }
38 if (i + z[i] - 1 > right) {
39 left = i;
40 right = i + z[i] - 1;
41 }
42 }
43 return z;
44 }
45
46 // Perform matrix multiplication and return the result.
47 vector<vector<int>> matrixMultiply(const vector<vector<int>>& a, const vector<vector<int>>& b) {
48 const int m = a.size(), n = b.size(), p = b[0].size();
49 vector<vector<int>> result(m, vector<int>(p, 0));
50 for (int i = 0; i < m; ++i) {
51 for (int j = 0; j < n; ++j) {
52 for (int k = 0; k < p; ++k) {
53 result[i][k] = add(result[i][k], mul(a[i][j], b[j][k]));
54 }
55 }
56 }
57 return result;
58 }
59
60 // Compute matrix exponentiation a^y and return the result.
61 vector<vector<int>> matrixPower(const vector<vector<int>>& a, long long y) {
62 const int n = a.size();
63 vector<vector<int>> res(n, vector<int>(n, 0));
64 for (int i = 0; i < n; ++i) {
65 res[i][i] = 1;
66 }
67 vector<vector<int>> x = a;
68 while (y) {
69 if (y & 1) {
70 res = matrixMultiply(res, x);
71 }
72 x = matrixMultiply(x, x);
73 y >>= 1;
74 }
75 return res;
76 }
77
78public:
79 // Calculate the number of ways 't' can be formed from 's' after 'k' operations.
80 int numberOfWays(const string& s, const string& t, long long k) {
81 const int n = s.length();
82
83 // Compute the dynamic programming base cases using matrix exponentiation.
84 const auto dpBaseCases = matrixPower({{0, 1}, {n - 1, n - 2}}, k)[0];
85
86 // Concatenate strings for z-array processing.
87 string concatenated = s + t + t;
88 const auto z = generateZArray(concatenated);
89 const int m = n + t.length();
90
91 // Calculate the result by checking z-values for string t's occurrences in s.
92 int result = 0;
93 for (int i = n; i < m; ++i) {
94 if (z[i] >= n) {
95 result = add(result, dpBaseCases[i - n != 0]);
96 }
97 }
98 return result;
99 }
100};
1011// Constant MOD to ensure modular arithmetic keeps values within integer bounds.
2const MOD: number = 1e9 + 7;
3
4// Functions and variables are defined globally as requested.
5
6// Utility function to perform addition under modulo.
7function add(x: number, y: number): number {
8 x += y;
9 if (x >= MOD) {
10 x -= MOD;
11 }
12 return x;
13}
14
15// Utility function to perform multiplication under modulo.
16function mul(x: number, y: number): number {
17 return Math.trunc((x * y) % MOD);
18}
19
20// Generate Z-array for string matching, used to find the number of matches of t in s.
21function generateZArray(s: string): number[] {
22 const n: number = s.length;
23 const z: number[] = new Array(n).fill(0);
24 for (let i = 1, left = 0, right = 0; i < n; ++i) {
25 if (i <= right && z[i - left] < right - i + 1) {
26 z[i] = z[i - left];
27 } else {
28 z[i] = Math.max(0, right - i + 1);
29 while (i + z[i] < n && s[i + z[i]] === s[z[i]]) {
30 ++z[i];
31 }
32 }
33 if (i + z[i] - 1 > right) {
34 left = i;
35 right = i + z[i] - 1;
36 }
37 }
38 return z;
39}
40
41// Perform matrix multiplication and return the result.
42function matrixMultiply(a: number[][], b: number[][]): number[][] {
43 const m: number = a.length;
44 const n: number = b.length;
45 const p: number = b[0].length;
46 const result: number[][] = Array.from({length: m}, () => new Array(p).fill(0));
47 for (let i = 0; i < m; ++i) {
48 for (let j = 0; j < n; ++j) {
49 for (let k = 0; k < p; ++k) {
50 result[i][k] = add(result[i][k], mul(a[i][j], b[j][k]));
51 }
52 }
53 }
54 return result;
55}
56
57// Compute matrix exponentiation a^y and return the result.
58function matrixPower(a: number[][], y: number): number[][] {
59 const n: number = a.length;
60 let res: number[][] = Array.from({length: n}, (_, index) => {
61 const row: number[] = new Array(n).fill(0);
62 row[index] = 1;
63 return row;
64 });
65 let x: number[][] = a.slice();
66
67 while (y) {
68 if (y & 1) {
69 res = matrixMultiply(res, x);
70 }
71 x = matrixMultiply(x, x);
72 y >>= 1;
73 }
74
75 return res;
76}
77
78// Calculate the number of ways 't' can be formed from 's' after 'k' operations.
79function numberOfWays(s: string, t: string, k: number): number {
80 const n: number = s.length;
81 // Compute the dynamic programming base cases using matrix exponentiation.
82 const dpBaseCases: number[][] = matrixPower([[0, 1], [n - 1, n - 2]], k);
83 // Concatenate strings for z-array processing.
84 const concatenated: string = s + t + t;
85 const z: number[] = generateZArray(concatenated);
86 const m: number = n + t.length;
87
88 // Calculate the result by checking z-values for string t's occurrences in s.
89 let result: number = 0;
90 for (let i = n; i < m; ++i) {
91 if (z[i] >= n) {
92 result = add(result, dpBaseCases[0][i - n !== 0 ? 1 : 0]);
93 }
94 }
95 return result;
96}
97Which algorithm should you use to find a node that is close to the root of the tree?
Time and Space Complexity
Time Complexity
The time complexity of the code consists of several parts, which are analyzed as follows:
-
Getting the Z-array: The function
getZuses the Z-algorithm to construct the Z-array for the concatenated strings + t + t. The complexity of this process isO(n)wherenis the length of the strings. -
Matrix Multiplication: The
matrixMultiplyfunction takes two matrices and multiplies them, which is used in the context of square matrices of size 2x2. The time complexity for this operation would beO(1)since we are dealing with a constant-size matrix. -
Matrix Exponentiation: The
matrixPowerfunction uses fast exponentiation to raise a matrix to the power ofk. The number of matrix multiplications required will beO(log k)because binary exponentiation is used. -
Overall Time Complexity: Combining these complexities, the total time complexity is
O(n + log k), which matches the provided time complexity analysis from the code comments.
Space Complexity
The space complexity is governed by the storage required for:
-
Z-array: The array
zthat holds the Z-values requiresO(n)space. -
Matrix Operations: The auxiliary space needed for the
matrixMultiplyandmatrixPowerfunctions uses a constant amount of additional space since only 2x2 matrices are involved. -
Total Space Complexity: Therefore, the total space complexity is
O(n), accounting for the storage of the Z-array and the constant space for matrix operations.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
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
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.