String Transformation

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 whichs can be transformed intot _inexactly _k operations.

Since the answer can be large, return it modulo 10^9 + 7.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3
4
5
6
7
8


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^5
1 <= k <= 1015
s.length == t.length
s and t consist of only lowercase English alphabets.

Solution

Method 1 - Cycle Decomposition and Matrix Exponentiation

Intuition

Each operation is a rotation of the string by l (1 ≤ l < n). All such rotations form a cyclic group. The problem reduces to counting the number of ways to reach t from s in exactly k steps, where each step is a non-trivial rotation. This is a Markov process on the n possible rotations.

Approach

Precompute all rotations of s and find which indices match t.
Let good = number of rotations of s that equal t, bad = n - good.
Let dp[i] = number of ways to reach a string equal to t after i steps.
The transition is: dp[i] = good * dp[i-1] + bad * (total - dp[i-1]), but can be solved with matrix exponentiation for efficiency.
Use fast exponentiation to compute the number of ways in O(log k) time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


MOD = 10**9 + 7

def string_transformation(s: str, t: str, k: int) -> int:
    n = len(s)
    # Find all rotations of s that match t
    good = 0
    for i in range(n):
        if s[i:] + s[:i] == t:
            good += 1
    bad = n - good
    # Markov chain: [ways to be at t, ways to not be at t]
    # Transition matrix:
    # [good-1, good]
    # [bad,   bad-1]
    # But since all rotations are reachable, we can use recurrence:
    # Let dp[0] = 1 if s == t else 0
    # dp[i] = good * dp[i-1] + bad * (total - dp[i-1])
    # This is equivalent to: dp[i] = (good-1)*dp[i-1] + bad*(n-1)^(i-1)
    # But we can use matrix exponentiation for the two states
    def mat_mult(a, b):
        return [
            [(a[0][0]*b[0][0] + a[0][1]*b[1][0]) % MOD, (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % MOD],
            [(a[1][0]*b[0][0] + a[1][1]*b[1][0]) % MOD, (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % MOD],
        ]
    def mat_pow(mat, power):
        res = [[1,0],[0,1]]
        while power:
            if power % 2:
                res = mat_mult(res, mat)
            mat = mat_mult(mat, mat)
            power //= 2
        return res
    # State: [at t, not at t]
    # Transition: [[good, bad], [good, bad]]
    trans = [[good-1, good], [bad, bad-1]]
    # Initial state: at t if s==t else not at t
    init = [1 if s == t else 0, 0 if s == t else 1]
    mat = mat_pow([[good-1, good], [bad, bad-1]], k)
    ans = (mat[0][0]*init[0] + mat[0][1]*init[1]) % MOD
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
    static final int MOD = 1_000_000_007;
    public int stringTransformation(String s, String t, long k) {
        int n = s.length();
        int good = 0;
        for (int i = 0; i < n; i++) {
            String rot = s.substring(i) + s.substring(0, i);
            if (rot.equals(t)) good++;
        }
        int bad = n - good;
        long[][] mat = {{good-1, good}, {bad, bad-1}};
        long[][] res = {{1,0},{0,1}};
        while (k > 0) {
            if ((k & 1) == 1) res = mult(res, mat);
            mat = mult(mat, mat);
            k >>= 1;
        }
        int init0 = s.equals(t) ? 1 : 0;
        int init1 = s.equals(t) ? 0 : 1;
        long ans = (res[0][0]*init0 + res[0][1]*init1) % MOD;
        return (int)ans;
    }
    private long[][] mult(long[][] a, long[][] b) {
        long[][] c = new long[2][2];
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD;
        return c;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


#include <string>
#include <vector>
using namespace std;
const int MOD = 1e9+7;
vector<vector<long long>> mult(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {
    vector<vector<long long>> c(2, vector<long long>(2));
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD;
    return c;
}
vector<vector<long long>> mat_pow(vector<vector<long long>> mat, long long k) {
    vector<vector<long long>> res = {{1,0},{0,1}};
    while (k) {
        if (k&1) res = mult(res, mat);
        mat = mult(mat, mat);
        k >>= 1;
    }
    return res;
}
int stringTransformation(string s, string t, long long k) {
    int n = s.size(), good = 0;
    for (int i = 0; i < n; ++i)
        if (s.substr(i) + s.substr(0, i) == t) good++;
    int bad = n - good;
    vector<vector<long long>> mat = {{good-1, good}, {bad, bad-1}};
    vector<vector<long long>> res = mat_pow(mat, k);
    int init0 = s == t ? 1 : 0, init1 = s == t ? 0 : 1;
    long long ans = (res[0][0]*init0 + res[0][1]*init1) % MOD;
    return (int)ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


const MOD int = 1e9+7
func stringTransformation(s, t string, k int64) int {
    n := len(s)
    good := 0
    for i := 0; i < n; i++ {
        if s[i:]+s[:i] == t {
            good++
        }
    }
    bad := n - good
    mat := [2][2]int{ {good-1, good}, {bad, bad-1} }
    res := [2][2]int{ {1,0}, {0,1} }
    for k > 0 {
        if k&1 == 1 {
            res = mult(res, mat)
        }
        mat = mult(mat, mat)
        k >>= 1
    }
    init0, init1 := 0, 1
    if s == t { init0, init1 = 1, 0 }
    ans := (res[0][0]*init0 + res[0][1]*init1) % MOD
    return ans
}
func mult(a, b [2][2]int) [2][2]int {
    var c [2][2]int
    for i := 0; i < 2; i++ {
        for j := 0; j < 2; j++ {
            for k := 0; k < 2; k++ {
                c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD
            }
        }
    }
    return c
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


const val MOD = 1_000_000_007
fun stringTransformation(s: String, t: String, k: Long): Int {
    val n = s.length
    var good = 0
    for (i in 0 until n) {
        if (s.substring(i) + s.substring(0, i) == t) good++
    }
    val bad = n - good
    fun mult(a: Array<LongArray>, b: Array<LongArray>): Array<LongArray> {
        val c = Array(2) { LongArray(2) }
        for (i in 0..1) for (j in 0..1) for (k in 0..1)
            c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD
        return c
    }
    fun matPow(mat: Array<LongArray>, k: Long): Array<LongArray> {
        var res = arrayOf(longArrayOf(1,0), longArrayOf(0,1))
        var m = mat
        var p = k
        while (p > 0) {
            if (p and 1L == 1L) res = mult(res, m)
            m = mult(m, m)
            p = p shr 1
        }
        return res
    }
    val mat = arrayOf(longArrayOf((good-1).toLong(), good.toLong()), longArrayOf(bad.toLong(), (bad-1).toLong()))
    val res = matPow(mat, k)
    val init0 = if (s == t) 1L else 0L
    val init1 = if (s == t) 0L else 1L
    val ans = (res[0][0]*init0 + res[0][1]*init1) % MOD
    return ans.toInt()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


const MOD: i64 = 1_000_000_007;
fn string_transformation(s: &str, t: &str, k: i64) -> i64 {
    let n = s.len();
    let mut good = 0;
    for i in 0..n {
        let rot = format!("{}{}", &s[i..], &s[..i]);
        if rot == t { good += 1; }
    }
    let bad = n as i64 - good;
    fn mult(a: [[i64;2];2], b: [[i64;2];2]) -> [[i64;2];2] {
        let mut c = [[0;2];2];
        for i in 0..2 { for j in 0..2 { for k in 0..2 {
            c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD;
        }}}
        c
    }
    fn mat_pow(mut mat: [[i64;2];2], mut k: i64) -> [[i64;2];2] {
        let mut res = [[1,0],[0,1]];
        while k > 0 {
            if k&1 == 1 { res = mult(res, mat); }
            mat = mult(mat, mat);
            k >>= 1;
        }
        res
    }
    let mat = [[good-1, good], [bad, bad-1]];
    let res = mat_pow(mat, k);
    let (init0, init1) = if s == t { (1,0) } else { (0,1) };
    (res[0][0]*init0 + res[0][1]*init1) % MOD
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


const MOD = 1e9+7;
function stringTransformation(s: string, t: string, k: number): number {
    const n = s.length;
    let good = 0;
    for (let i = 0; i < n; i++) {
        if (s.slice(i) + s.slice(0, i) === t) good++;
    }
    const bad = n - good;
    function mult(a: number[][], b: number[][]): number[][] {
        const c = [ [0,0], [0,0] ];
        for (let i = 0; i < 2; i++)
            for (let j = 0; j < 2; j++)
                for (let k = 0; k < 2; k++)
                    c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % MOD;
        return c;
    }
    function matPow(mat: number[][], k: number): number[][] {
        let res = [ [1,0], [0,1] ];
        while (k > 0) {
            if (k & 1) res = mult(res, mat);
            mat = mult(mat, mat);
            k >>= 1;
        }
        return res;
    }
    const mat = [ [good-1, good], [bad, bad-1] ];
    const res = matPow(mat, k);
    const init0 = s === t ? 1 : 0, init1 = s === t ? 0 : 1;
    const ans = (res[0][0]*init0 + res[0][1]*init1) % MOD;
    return ans;
}

Complexity

⏰ Time complexity: O(n + log k)
🧺 Space complexity: O(1)

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 - Cycle Decomposition and Matrix Exponentiation#

Intuition#

Approach#

Code#

Complexity#