2851. String Transformation

HardMathStringDynamic ProgrammingString Matching
Leetcode Link

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.

  1. String Representation: Since each operation is essentially a rotation of the string s, you can represent the resulting string using an integer from 0 to n - 1, indicating the new index of the original first character of s.

  2. Target String Representation: By concatenating s + t + t, and using the Z-algorithm, you can find all valid rotations of s that match t. A rotation is valid if a substring starting at an index in [n, 2n) is a prefix match to t that covers the entire length of t.

  3. Dynamic Programming: The DP equation considers two states:

    • dp[t][0] is the number of ways to return to the original string after t operations.
    • dp[t][1] is the number of ways to have a non-original string after t operations.

  4. State Transition: The transitions are:

    • From a non-original to the original string, it's always possible with n - 1 ways (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 - 2 ways (since you can't pick the suffix that transforms the string to itself).

  5. 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 power k, 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.

Solution Approach

The solution's implementation can be outlined in the following steps:

  1. String Representation & Z-algorithm:

    • Concatenate s, t, and t again to create a new string on which Z-algorithm is applied. This algorithm runs in O(n) time and creates a Z-array z where z[i] represents the length of the longest substring starting from i that matches the prefix of the string.
    • A valid rotation of s that can match t is identified if there's a prefix match of length n starting at positions in the range [n, 2n) in the concatenated string.

  2. Dynamic Programming Set-up:

    • Define DP states dp[t][0] and dp[t][1] where t is the number of operations and the second index indicates whether the string is the original (0) or a rotation (1).

  3. 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.

  4. 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.

  5. 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.

  6. Considering Valid Rotations:

    • After calculating dp = matrixPower([[0, 1], [n - 1, n - 2]], k)[0], iterate for each index i in [n, 2n) and if z[i] indicates a valid rotation, accumulate dp[0] if it is an original string (i - n == 0) or dp[1] otherwise.

  7. Final Result:

    • Since we're interested in finding the number of ways modulo 10^9 + 7, all additions and multiplications are done modulo M.

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).

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach:

  • Let s = "ab", t = "ba", and k = 2.

We need to determine the number of ways to transform s into t using exactly k operations.

  1. String Representation & Z-algorithm:

    • We concatenate s + t + t which gives "abbaab".
    • Applying the Z-algorithm on this string, we get the Z-array: z = [0, 0, 1, 2, 1, 0]. What matters are elements z[2] = 1 and z[3] = 2.
    • We see that z[3] = 2 implies there is a rotation, by moving the suffix "ab" to the front, that matches t.

  2. Dynamic Programming Set-up:

    • We define a 2D DP array where dp[i][0] is the number of ways to have the original string after i operations, and dp[i][1] is for the non-original strings.

  3. State Transitions:

    • We establish the transitions dp[t][0] = dp[t - 1][1] * 1 (since n - 1 = 2 - 1 = 1 here) and dp[t][1] = dp[t - 1][0] + dp[t - 1][1] * 0.

  4. Matrix Multiplication:

    • The transition matrix for our example is [ [0, 1], [1, 0] ] since n = 2.
    • We need to calculate the matrix raised to the power of k, which is 2.

  5. The Matrix Power Function:

    • The function used to raise our matrix to the power of k will essentially compute matrix^2.
    • After the computation, we get that the raised matrix is still [ [0, 1], [1, 0] ].

  6. 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.

  7. 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 consider dp[1], but since dp[1] = 0, there are no valid ways for this example.
    • The final result is 0 modulo 10^9 + 7.

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
67
1class 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}
92
1#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};
101
1// 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}
97

Time and Space Complexity

Time Complexity

The time complexity of the code consists of several parts, which are analyzed as follows:

  1. Getting the Z-array: The function getZ uses the Z-algorithm to construct the Z-array for the concatenated string s + t + t. The complexity of this process is O(n) where n is the length of the string s.

  2. Matrix Multiplication: The matrixMultiply function 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 be O(1) since we are dealing with a constant-size matrix.

  3. Matrix Exponentiation: The matrixPower function uses fast exponentiation to raise a matrix to the power of k. The number of matrix multiplications required will be O(log k) because binary exponentiation is used.

  4. 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:

  1. Z-array: The array z that holds the Z-values requires O(n) space.

  2. Matrix Operations: The auxiliary space needed for the matrixMultiply and matrixPower functions uses a constant amount of additional space since only 2x2 matrices are involved.

  3. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode 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 we

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More