String Transformation

Hard

#2550Time: 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)`.3 companies

Patterns

Math Dynamic Programming String Matching

Data structures

String

Companies

Atlassian Snowflake MathWorks

Prompt

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 s of length l where 0 < l < n and append it at the start of s.
For example, let s = 'abcd' then in one operation you can remove the suffix 'cd' and append it in front of s making s = '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 10⁹ + 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 * 10⁵
1 <= k <= 10¹⁵
s.length == t.length
s and t consist 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 t is a cyclic shift of s. This can be done by checking if s.length() == t.length() and if (s + s).contains(t). If t is not a cyclic shift, it's impossible to transform s to t, so the answer is 0.
The core idea is to model the problem as counting paths of length k in a state graph. The states are the distinct cyclic shifts of s.
Find the number of distinct cyclic shifts of s. This is equal to the length of the smallest period of s, let's call it g. We can find g in O(n) time using the Knuth-Morris-Pratt (KMP) algorithm's preprocessing step (LPS array).
Let the g distinct cyclic shifts be the states of our graph. We can construct a g x g transition matrix M, where M[i][j] is the number of ways to transition from state i to state j in one operation.
The number of ways to stay in the same state (e.g., from u to u) is A = n/g - 1. This is because a shift operation leaves the string unchanged only if the shift amount is a multiple of the period g. There are n/g - 1 such non-zero shift amounts possible.
The number of ways to move from one state u to a different specific state v is B = n/g. There are n/g shift amounts that will transform u into v.
So, the transition matrix M will have A on its diagonal and B everywhere else.
Create an initial state vector v_0 of size g. If s is the i-th distinct shift, v_0 will have a 1 at index i and 0s elsewhere. If s is the same as t (let's say the 0-th state), v_0 = [1, 0, ..., 0]^T.
The number of ways to be in each state after k operations is given by the vector v_k = M^k * v_0.
We can compute M^k efficiently using binary exponentiation (also known as exponentiation by squaring) for matrices. This takes O(g^3 log k) time.
The final answer is the element of v_k corresponding to the state t.

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.

1// This is a conceptual illustration. It would be too slow to pass.2// Assuming we have a function to compute g and the transition matrix M.3 4long[][] multiply(long[][] A, long[][] B, int g, long mod) {5    long[][] C = new long[g][g];6    for (int i = 0; i < g; i++) {7        for (int j = 0; j < g; j++) {8            for (int l = 0; l < g; l++) {9                C[i][j] = (C[i][j] + A[i][l] * B[l][j]) % mod;10            }11        }12    }13    return C;14}15 16long[][] matrixPower(long[][] M, long k, int g, long mod) {17    long[][] res = new long[g][g];18    for (int i = 0; i < g; i++) res[i][i] = 1;19    while (k > 0) {20        if (k % 2 == 1) res = multiply(res, M, g, mod);21        M = multiply(M, M, g, mod);22        k /= 2;23    }24    return res;25}26 27// In the main function:28// 1. Compute g.29// 2. Build the g x g matrix M.30// 3. Compute M_k = matrixPower(M, k, g, MOD).31// 4. Determine initial vector v_0.32// 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 given n can be up to 5 * 10^5, as g can be equal to n in the worst case.
The space complexity of O(g^2) can also be too large.

A highly efficient approach involves deriving and solving a linear recurrence relation for the number of ways to obtain the target string t. By classifying the states into two categories—being at t or not being at t—we can establish a relationship between the number of ways after k steps and k+1 steps. This recurrence can be solved to yield a direct formula for the answer. The formula involves terms like (n-1)^k and (-1)^k, which can be computed quickly using modular exponentiation. This avoids the expensive matrix operations entirely.

Algorithm

First, handle the base case: if t is not a cyclic shift of s, return 0. This is checked by (s + s).contains(t).
The problem can be simplified by setting up a recurrence relation. Let w_k be the number of ways to obtain string t in k steps. The key insight is that the transition counts are uniform across all states due to the cyclic nature of the operations.
Find g, the length of the smallest period of s, using the KMP algorithm's LPS array. The number of distinct cyclic shifts is g.
The number of ways to perform an operation that results in the same string is A = n/g - 1.
The number of ways to transition from one specific string u to another specific string v (u != v) is B = n/g.
The number of ways to be at t after k+1 steps, w_{k+1}, can be expressed in terms of w_k. A path can arrive at t either from t itself or from any other string s' != t. This gives the recurrence: w_{k+1} = w_k * A + ( ext{ways from non-t states}). The total number of paths of length k is (n-1)^k. The number of paths ending at a non-t state is (n-1)^k - w_k. This leads to the recurrence w_{k+1} = (A-B)w_k + B(n-1)^k, which simplifies to w_{k+1} = -w_k + (n/g)(n-1)^k.
This linear recurrence relation can be solved to find a closed-form formula for w_k.
If s == t, the initial condition is w_0 = 1. The solution is w_k = (inv_g * (n-1)^k + (g-1) * inv_g * (-1)^k) mod MOD.
If s != t, the initial condition is w_0 = 0. The solution is w_k = (inv_g * ((n-1)^k - (-1)^k)) mod MOD.
inv_g is the modular multiplicative inverse of g. We can compute powers using modular exponentiation.

Walkthrough

This approach leverages mathematical analysis to find a direct formula. First, we find the smallest period g of s using KMP's LPS array computation in O(n) time. The number of distinct cyclic shifts is g.

The number of ways to transition from any shift to itself is A = n/g - 1. The number of ways to transition from one shift u to another specific shift v is B = n/g.

Let w_k be the number of ways to be at t after k steps. The total number of paths of length k is (n-1)^k. The recurrence for w_k is w_{k+1} = -w_k + B imes (n-1)^k. Solving this gives a closed-form solution depending on w_0.

If s == t, w_0 = 1. The number of ways is w_k = (inv_g imes (n-1)^k + (1 - inv_g) imes (-1)^k) ext{ mod } MOD.
If s != t, w_0 = 0. The number of ways is w_k = (inv_g imes ((n-1)^k - (-1)^k)) ext{ mod } MOD.

We can implement this using modular exponentiation for powers and for finding the modular inverse of g.

1class Solution {2    long MOD = 1_000_000_007;3 4    public int numberOfWays(String s, String t, long k) {5        int n = s.length();6        if (!(s + s).contains(t)) {7            return 0;8        }9 10        int g = getPeriod(s);11 12        long nMinus1_k = power(n - 1, k);13        long minus1_k = (k % 2 == 0) ? 1 : MOD - 1;14 15        long inv_g = power(g, MOD - 2);16 17        long ans;18        if (s.equals(t)) {19            // w_k = (1/g) * (n-1)^k + (g-1)/g * (-1)^k20            long term1 = (inv_g * nMinus1_k) % MOD;21            long g_minus_1 = (g - 1 + MOD) % MOD;22            long term2_factor = (g_minus_1 * inv_g) % MOD;23            long term2 = (term2_factor * minus1_k) % MOD;24            ans = (term1 + term2) % MOD;25        } else {26            // w_k = (1/g) * ((n-1)^k - (-1)^k)27            long term1 = (nMinus1_k - minus1_k + MOD) % MOD;28            ans = (inv_g * term1) % MOD;29        }30        return (int) ans;31    }32 33    private long power(long base, long exp) {34        long res = 1;35        base %= MOD;36        while (exp > 0) {37            if (exp % 2 == 1) res = (res * base) % MOD;38            base = (base * base) % MOD;39            exp /= 2;40        }41        return res;42    }43 44    private int getPeriod(String s) {45        int n = s.length();46        int[] lps = new int[n];47        for (int i = 1; i < n; i++) {48            int j = lps[i - 1];49            while (j > 0 && s.charAt(i) != s.charAt(j)) {50                j = lps[j - 1];51            }52            if (s.charAt(i) == s.charAt(j)) {53                j++;54            }55            lps[i] = j;56        }57        int len = lps[n - 1];58        if (n % (n - len) == 0) {59            return n - len;60        }61        return n;62    }63}

Complexity

Time

O(n + log k). `O(n)` is for checking if `t` is a shift and for computing the period `g`. `O(log k)` is for the modular exponentiation operations.

Space

O(n), primarily for the LPS array used in the KMP algorithm to find the string's period.

Trade-offs

Pros

Extremely efficient with a time complexity of O(n + log k), which easily passes the given constraints.
Low space complexity, only requiring O(n) for KMP preprocessing.

Cons

The derivation of the recurrence relation and its solution is more complex than the direct matrix exponentiation model.
Requires knowledge of string algorithms (KMP for period) and number theory (modular inverse).

Solutions

Solution

1class Solution {2private3  static final int M = 1000000007;4private5  int add(int x, int y) {6    if ((x += y) >= M) {7      x -= M;8    }9    return x;10  }11private12  int mul(long x, long y) { return (int)(x * y % M); }13private14  int[] getZ(String s) {15    int n = s.length();16    int[] z = new int[n];17    for (int i = 1, left = 0, right = 0; i < n; ++i) {18      if (i <= right && z[i - left] <= right - i) {19        z[i] = z[i - left];20      } else {21        int z_i = Math.max(0, right - i + 1);22        while (i + z_i < n && s.charAt(i + z_i) == s.charAt(z_i)) {23          z_i++;24        }25        z[i] = z_i;26      }27      if (i + z[i] - 1 > right) {28        left = i;29        right = i + z[i] - 1;30      }31    }32    return z;33  }34private35  int[][] matrixMultiply(int[][] a, int[][] b) {36    int m = a.length, n = a[0].length, p = b[0].length;37    int[][] r = new int[m][p];38    for (int i = 0; i < m; ++i) {39      for (int j = 0; j < p; ++j) {40        for (int k = 0; k < n; ++k) {41          r[i][j] = add(r[i][j], mul(a[i][k], b[k][j]));42        }43      }44    }45    return r;46  }47private48  int[][] matrixPower(int[][] a, long y) {49    int n = a.length;50    int[][] r = new int[n][n];51    for (int i = 0; i < n; ++i) {52      r[i][i] = 1;53    }54    int[][] x = new int[n][n];55    for (int i = 0; i < n; ++i) {56      System.arraycopy(a[i], 0, x[i], 0, n);57    }58    while (y > 0) {59      if ((y & 1) == 1) {60        r = matrixMultiply(r, x);61      }62      x = matrixMultiply(x, x);63      y >>= 1;64    }65    return r;66  }67public68  int numberOfWays(String s, String t, long k) {69    int n = s.length();70    int[] dp = matrixPower(new int[][]{{0, 1}, {n - 1, n - 2}}, k)[0];71    s += t + t;72    int[] z = getZ(s);73    int m = n + n;74    int result = 0;75    for (int i = n; i < m; ++i) {76      if (z[i] >= n) {77        result = add(result, dp[i - n == 0 ? 0 : 1]);78      }79    }80    return result;81  }82}

1class Solution {2  const int M = 1000000007;3  int add(int x, int y) {4    if ((x += y) >= M) {5      x -= M;6    }7    return x;8  }9  int mul(long long x, long long y) { return x * y % M; }10  vector<int> getz(const string &s) {11    const int n = s.length();12    vector<int> z(n);13    for (int i = 1, left = 0, right = 0; i < n; ++i) {14      if (i <= right && z[i - left] <= right - i) {15        z[i] = z[i - left];16      } else {17        for (z[i] = max(0, right - i + 1);18             i + z[i] < n && s[i + z[i]] == s[z[i]]; ++z[i])19          ;20      }21      if (i + z[i] - 1 > right) {22        left = i;23        right = i + z[i] - 1;24      }25    }26    return z;27  }28  vector<vector<int>> mul(const vector<vector<int>> &a,29                          const vector<vector<int>> &b) {30    const int m = a.size(), n = a[0].size(), p = b[0].size();31    vector<vector<int>> r(m, vector<int>(p));32    for (int i = 0; i < m; ++i) {33      for (int j = 0; j < n; ++j) {34        for (int k = 0; k < p; ++k) {35          r[i][k] = add(r[i][k], mul(a[i][j], b[j][k]));36        }37      }38    }39    return r;40  }41  vector<vector<int>> pow(const vector<vector<int>> &a, long long y) {42    const int n = a.size();43    vector<vector<int>> r(n, vector<int>(n));44    for (int i = 0; i < n; ++i) {45      r[i][i] = 1;46    }47    auto x = a;48    for (; y; y >>= 1) {49      if (y & 1) {50        r = mul(r, x);51      }52      x = mul(x, x);53    }54    return r;55  }56 57public:58  int numberOfWays(string s, string t, long long k) {59    const int n = s.length();60    const auto dp = pow({{0, 1}, {n - 1, n - 2}}, k)[0];61    s.append(t);62    s.append(t);63    const auto z = getz(s);64    const int m = n + n;65    int r = 0;66    for (int i = n; i < m; ++i) {67      if (z[i] >= n) {68        r = add(r, dp[!!(i - n)]);69      }70    }71    return r;72  }73};

1""" DP, Z-algorithm, Fast mod. Approach How to represent a string? Each operation is just a rotation. Each result string can be represented by an integer from 0 to n - 1. Namely, it's just the new index of s[0]. How to find the integer(s) that can represent string t? Create a new string s + t + t (length = 3 * n). Use Z-algorithm (or KMP), for each n <= index < 2 * n, calculate the maximum prefix length that each substring starts from index can match, if the length >= n, then (index - n) is a valid integer representation. How to get the result? It's a very obvious DP. If we use an integer to represent a string, we only need to consider the transition from zero to non-zero and from non-zero to zero. In other words, all the non-zero strings should have the same result. So let dp[t][i = 0/1] be the number of ways to get the zero/nonzero string after excatly t steps. Then dp[t][0] = dp[t - 1][1] * (n - 1). All the non zero strings can make it. dp[t][1] = dp[t - 1][0] + dp[t - 1] * (n - 2). For a particular non zero string, all the other non zero strings and zero string can make it. We have dp[0][0] = 1 and dp[0][1] = 0 Use matrix multiplication. How to calculate dp[k][x = 0, 1] faster? Use matrix multiplication vector (dp[t - 1][0], dp[t - 1][1]) multiplies matrix [0 1] [n - 1 n - 2] == vector (dp[t][0], dp[t - 1][1]). So we just need to calculate the kth power of the matrix which can be done by fast power algorith. Complexity Time complexity: O(n + logk) Space complexity: O(n) """ class Solution : M : int = 1000000007 def add ( self , x : int , y : int ) -> int : x += y if x >= self . M : x -= self . M return x def mul ( self , x : int , y : int ) -> int : return int ( x * y % self . M ) def getZ ( self , s : str ) -> List [ int ]: n = len ( s ) z = [ 0 ] * n left = right = 0 for i in range ( 1 , n ): if i <= right and z [ i - left ] <= right - i : z [ i ] = z [ i - left ] else : z_i = max ( 0 , right - i + 1 ) while i + z_i < n and s [ i + z_i ] == s [ z_i ]: z_i += 1 z [ i ] = z_i if i + z [ i ] - 1 > right : left = i right = i + z [ i ] - 1 return z def matrixMultiply ( self , a : List [ List [ int ]], b : List [ List [ int ]]) -> List [ List [ int ]]: m = len ( a ) n = len ( a [ 0 ]) p = len ( b [ 0 ]) r = [[ 0 ] * p for _ in range ( m )] for i in range ( m ): for j in range ( p ): for k in range ( n ): r [ i ][ j ] = self . add ( r [ i ][ j ], self . mul ( a [ i ][ k ], b [ k ][ j ])) return r def matrixPower ( self , a : List [ List [ int ]], y : int ) -> List [ List [ int ]]: n = len ( a ) r = [[ 0 ] * n for _ in range ( n )] for i in range ( n ): r [ i ][ i ] = 1 x = [ a [ i ][:] for i in range ( n )] while y > 0 : if y & 1 : r = self . matrixMultiply ( r , x ) x = self . matrixMultiply ( x , x ) y >>= 1 return r def numberOfWays ( self , s : str , t : str , k : int ) -> int : n = len ( s ) dp = self . matrixPower ([[ 0 , 1 ], [ n - 1 , n - 2 ]], k )[ 0 ] s += t + t z = self . getZ ( s ) m = n + n result = 0 for i in range ( n , m ): if z [ i ] >= n : result = self . add ( result , dp [ 0 ] if i - n == 0 else dp [ 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.

← Previous

Previous problem

Next problem