String Transformation
HardPrompt
You are given two strings s and t of equal length n. You can perform the following operation on the string s:
- Remove a suffix of
sof lengthlwhere0 < l < nand append it at the start ofs.
For example, lets = 'abcd'then in one operation you can remove the suffix'cd'and append it in front ofsmakings = 'cdab'.
You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.
Since the answer can be large, return it modulo 109 + 7.
Example 1:
Input: s = "abcd", t = "cdab", k = 2
Output: 2
Explanation:
First way:
In first operation, choose suffix from index = 3, so resulting s = "dabc".
In second operation, choose suffix from index = 3, so resulting s = "cdab".
Second way:
In first operation, choose suffix from index = 1, so resulting s = "bcda".
In second operation, choose suffix from index = 1, so resulting s = "cdab".Example 2:
Input: s = "ababab", t = "ababab", k = 1
Output: 2
Explanation:
First way:
Choose suffix from index = 2, so resulting s = "ababab".
Second way:
Choose suffix from index = 4, so resulting s = "ababab".
Constraints:
2 <= s.length <= 5 * 1051 <= k <= 1015s.length == t.lengthsandtconsist of only lowercase English alphabets.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as a path-counting problem on a state graph. The states are the distinct cyclic shifts of the string s. We can determine the number of ways to transition between any two states in a single operation. These transition counts form a g x g matrix, where g is the number of distinct cyclic shifts. We can then use matrix exponentiation to find the number of ways to reach the target state t in k steps. While conceptually clear, this method is generally too slow for the given constraints.
Algorithm
- First, check if
tis a cyclic shift ofs. This can be done by checking ifs.length() == t.length()and if(s + s).contains(t). Iftis not a cyclic shift, it's impossible to transformstot, so the answer is 0. - The core idea is to model the problem as counting paths of length
kin a state graph. The states are the distinct cyclic shifts ofs. - Find the number of distinct cyclic shifts of
s. This is equal to the length of the smallest period ofs, let's call itg. We can findginO(n)time using the Knuth-Morris-Pratt (KMP) algorithm's preprocessing step (LPS array). - Let the
gdistinct cyclic shifts be the states of our graph. We can construct ag x gtransition matrixM, whereM[i][j]is the number of ways to transition from stateito statejin one operation. - The number of ways to stay in the same state (e.g., from
utou) isA = n/g - 1. This is because a shift operation leaves the string unchanged only if the shift amount is a multiple of the periodg. There aren/g - 1such non-zero shift amounts possible. - The number of ways to move from one state
uto a different specific statevisB = n/g. There aren/gshift amounts that will transformuintov. - So, the transition matrix
Mwill haveAon its diagonal andBeverywhere else. - Create an initial state vector
v_0of sizeg. Ifsis thei-th distinct shift,v_0will have a 1 at indexiand 0s elsewhere. Ifsis the same ast(let's say the 0-th state),v_0 = [1, 0, ..., 0]^T. - The number of ways to be in each state after
koperations is given by the vectorv_k = M^k * v_0. - We can compute
M^kefficiently using binary exponentiation (also known as exponentiation by squaring) for matrices. This takesO(g^3 log k)time. - The final answer is the element of
v_kcorresponding to the statet.
Walkthrough
The problem asks for the number of ways to transform s to t in k operations. Each operation is a cyclic shift. The set of all strings reachable from s is the set of its cyclic shifts. Let g be the number of distinct cyclic shifts of s. We can define a g x g transition matrix M where M[i][j] is the number of ways to go from the i-th distinct shift to the j-th in one step. It can be shown that M[i][i] = n/g - 1 and M[i][j] = n/g for i != j. We need to find (M^k * v_0)_t, where v_0 is the initial state vector and t is the target state index. Matrix exponentiation by squaring allows computing M^k in O(g^3 log k) time.
// This is a conceptual illustration. It would be too slow to pass.// Assuming we have a function to compute g and the transition matrix M. long[][] multiply(long[][] A, long[][] B, int g, long mod) { long[][] C = new long[g][g]; for (int i = 0; i < g; i++) { for (int j = 0; j < g; j++) { for (int l = 0; l < g; l++) { C[i][j] = (C[i][j] + A[i][l] * B[l][j]) % mod; } } } return C;} long[][] matrixPower(long[][] M, long k, int g, long mod) { long[][] res = new long[g][g]; for (int i = 0; i < g; i++) res[i][i] = 1; while (k > 0) { if (k % 2 == 1) res = multiply(res, M, g, mod); M = multiply(M, M, g, mod); k /= 2; } return res;} // In the main function:// 1. Compute g.// 2. Build the g x g matrix M.// 3. Compute M_k = matrixPower(M, k, g, MOD).// 4. Determine initial vector v_0.// 5. Compute result M_k * v_0.Complexity
Time
O(n + g^3 log k). `O(n)` is for finding `g`. `O(g^3 log k)` is for matrix exponentiation. Since `g` can be up to `n`, the worst-case complexity is `O(n^3 log k)`.
Space
O(n + g^2), where `n` is the string length and `g` is the number of distinct cyclic shifts. `O(n)` is for KMP preprocessing and `O(g^2)` is for storing the transition matrix. In the worst case, `g=n`, so it's `O(n^2)`.
Trade-offs
Pros
This is a standard and intuitive technique for solving problems involving counting paths of a fixed length in a graph.
It correctly models the state transitions.
Cons
The time complexity of
O(g^3 log k)is too slow givenncan be up to5 * 10^5, asgcan be equal tonin the worst case.The space complexity of
O(g^2)can also be too large.
Solutions
Solution
class Solution {private static final int M = 1000000007;private int add(int x, int y) { if ((x += y) >= M) { x -= M; } return x; }private int mul(long x, long y) { return (int)(x * y % M); }private int[] getZ(String s) { int n = s.length(); int[] z = new int[n]; for (int i = 1, left = 0, right = 0; i < n; ++i) { if (i <= right && z[i - left] <= right - i) { z[i] = z[i - left]; } else { int z_i = Math.max(0, right - i + 1); while (i + z_i < n && s.charAt(i + z_i) == s.charAt(z_i)) { z_i++; } z[i] = z_i; } if (i + z[i] - 1 > right) { left = i; right = i + z[i] - 1; } } return z; }private int[][] matrixMultiply(int[][] a, int[][] b) { int m = a.length, n = a[0].length, p = b[0].length; int[][] r = new int[m][p]; for (int i = 0; i < m; ++i) { for (int j = 0; j < p; ++j) { for (int k = 0; k < n; ++k) { r[i][j] = add(r[i][j], mul(a[i][k], b[k][j])); } } } return r; }private int[][] matrixPower(int[][] a, long y) { int n = a.length; int[][] r = new int[n][n]; for (int i = 0; i < n; ++i) { r[i][i] = 1; } int[][] x = new int[n][n]; for (int i = 0; i < n; ++i) { System.arraycopy(a[i], 0, x[i], 0, n); } while (y > 0) { if ((y & 1) == 1) { r = matrixMultiply(r, x); } x = matrixMultiply(x, x); y >>= 1; } return r; }public int numberOfWays(String s, String t, long k) { int n = s.length(); int[] dp = matrixPower(new int[][]{{0, 1}, {n - 1, n - 2}}, k)[0]; s += t + t; int[] z = getZ(s); int m = n + n; int result = 0; for (int i = n; i < m; ++i) { if (z[i] >= n) { result = add(result, dp[i - n == 0 ? 0 : 1]); } } return result; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.