# String Transformation
**Difficulty:** HARD
[External](https://leetcode.com/problems/string-transformation)
Canonical: https://scaleengineer.com/dsa/problems/string-transformation
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Snowflake](https://scaleengineer.com/companies/snowflake), [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## Problem
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** `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 * 105`
* `1 <= k <= 1015`
* `s.length == t.length`
* `s` and `t` consist of only lowercase English alphabets.

# Approaches
## Matrix Exponentiation on Distinct States
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.
**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)`.
**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.
### Explanation
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.

```java
// 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.
```
### Algorithm
1.  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.
2.  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`.
3.  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).
4.  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.
5.  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.
6.  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`.
7.  So, the transition matrix `M` will have `A` on its diagonal and `B` everywhere else.
8.  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`.
9.  The number of ways to be in each state after `k` operations is given by the vector `v_k = M^k * v_0`.
10. 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.
11. The final answer is the element of `v_k` corresponding to the state `t`.

## Mathematical Approach via Recurrence Relation
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.
**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.
**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).
### Explanation
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`.

```java
class Solution {
    long MOD = 1_000_000_007;

    public int numberOfWays(String s, String t, long k) {
        int n = s.length();
        if (!(s + s).contains(t)) {
            return 0;
        }

        int g = getPeriod(s);

        long nMinus1_k = power(n - 1, k);
        long minus1_k = (k % 2 == 0) ? 1 : MOD - 1;

        long inv_g = power(g, MOD - 2);

        long ans;
        if (s.equals(t)) {
            // w_k = (1/g) * (n-1)^k + (g-1)/g * (-1)^k
            long term1 = (inv_g * nMinus1_k) % MOD;
            long g_minus_1 = (g - 1 + MOD) % MOD;
            long term2_factor = (g_minus_1 * inv_g) % MOD;
            long term2 = (term2_factor * minus1_k) % MOD;
            ans = (term1 + term2) % MOD;
        } else {
            // w_k = (1/g) * ((n-1)^k - (-1)^k)
            long term1 = (nMinus1_k - minus1_k + MOD) % MOD;
            ans = (inv_g * term1) % MOD;
        }
        return (int) ans;
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    private int getPeriod(String s) {
        int n = s.length();
        int[] lps = new int[n];
        for (int i = 1; i < n; i++) {
            int j = lps[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = lps[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            lps[i] = j;
        }
        int len = lps[n - 1];
        if (n % (n - len) == 0) {
            return n - len;
        }
        return n;
    }
}
```
### Algorithm
1.  First, handle the base case: if `t` is not a cyclic shift of `s`, return 0. This is checked by `(s + s).contains(t)`.
2.  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.
3.  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`.
4.  The number of ways to perform an operation that results in the same string is `A = n/g - 1`.
5.  The number of ways to transition from one specific string `u` to another specific string `v` (`u != v`) is `B = n/g`.
6.  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`.
7.  This linear recurrence relation can be solved to find a closed-form formula for `w_k`.
8.  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`.
9.  If `s != t`, the initial condition is `w_0 = 0`. The solution is `w_k = (inv_g * ((n-1)^k - (-1)^k)) mod MOD`.
10. `inv_g` is the modular multiplicative inverse of `g`. We can compute powers using modular exponentiation.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
  const int M = 1000000007;
  int add(int x, int y) {
    if ((x += y) >= M) {
      x -= M;
    }
    return x;
  }
  int mul(long long x, long long y) { return x * y % M; }
  vector<int> getz(const string &s) {
    const int n = s.length();
    vector<int> z(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 {
        for (z[i] = max(0, right - i + 1);
             i + z[i] < n && s[i + z[i]] == s[z[i]]; ++z[i])
          ;
      }
      if (i + z[i] - 1 > right) {
        left = i;
        right = i + z[i] - 1;
      }
    }
    return z;
  }
  vector<vector<int>> mul(const vector<vector<int>> &a,
                          const vector<vector<int>> &b) {
    const int m = a.size(), n = a[0].size(), p = b[0].size();
    vector<vector<int>> r(m, vector<int>(p));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        for (int k = 0; k < p; ++k) {
          r[i][k] = add(r[i][k], mul(a[i][j], b[j][k]));
        }
      }
    }
    return r;
  }
  vector<vector<int>> pow(const vector<vector<int>> &a, long long y) {
    const int n = a.size();
    vector<vector<int>> r(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      r[i][i] = 1;
    }
    auto x = a;
    for (; y; y >>= 1) {
      if (y & 1) {
        r = mul(r, x);
      }
      x = mul(x, x);
    }
    return r;
  }

public:
  int numberOfWays(string s, string t, long long k) {
    const int n = s.length();
    const auto dp = pow({{0, 1}, {n - 1, n - 2}}, k)[0];
    s.append(t);
    s.append(t);
    const auto z = getz(s);
    const int m = n + n;
    int r = 0;
    for (int i = n; i < m; ++i) {
      if (z[i] >= n) {
        r = add(r, dp[!!(i - n)]);
      }
    }
    return r;
  }
};

```

### Python

```python
""" 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
```