LeetCode 2851 - String Transformation

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming, String Matching

Solution

Problem Understanding

The problem asks us to transform a string s into a target string t using a very specific operation: choosing a non-empty suffix of s (not the whole string) and moving it to the front. The operation can be repeated exactly k times, and we are asked to count the number of distinct sequences of such operations that result in t.

The input consists of two strings of equal length n (up to 500,000) and an integer k that can be as large as $10^{15}$. The output is the number of ways to achieve the transformation, modulo $10^9 + 7$.

Important points:

Only suffix rotations are allowed, which preserves the relative order of characters.
We are counting sequences of operations, not just whether the transformation is possible.
k can be extremely large, so naive simulation of each operation is infeasible.
Strings can be equal, which allows trivial rotations to count as valid transformations.

Edge cases that are likely to cause naive implementations to fail include:

s equals t - multiple rotations may still count as valid operations.
Very large k - iterating through k operations is impossible.
Strings with repeating patterns, e.g., "ababab" - multiple rotations can lead to the same result.

Approaches

Brute Force

A brute-force approach would attempt to generate all possible sequences of k suffix rotations on s and count how many lead to t. For each rotation, we could try every suffix from length 1 to n-1.

This approach is correct in principle because it exhaustively checks all sequences, but the complexity is exponential: $O((n-1)^k)$, which is utterly infeasible for the input constraints, especially since k can be $10^{15}$.

Key Insight for Optimal Solution

The key observation is that a rotation by a suffix is equivalent to a cyclic rotation of the string. All possible transformations of s through one operation are rotations of s by some number of positions.

Let shift be the number of characters moved from the end to the start. Then, after one operation, s becomes s[-shift:] + s[:-shift]. If we precompute all shift values such that s rotated by shift equals t, the problem reduces to counting sequences of moves that sum modulo n to one of these valid shifts, taking into account that we have exactly k moves.

If s != t, there are specific rotations that reach t in one operation, otherwise the first move must avoid the identity rotation. The number of sequences can then be computed using modular exponentiation and combinatorial counting with the formula for repeated independent choices.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((n-1)^k)	O(n)	Generate all sequences of rotations; infeasible for large `k`
Optimal	O(n + log k)	O(n)	Use rotation checks, modular exponentiation, combinatorics

Algorithm Walkthrough

Identify Valid Rotations: Compute all shift values $1 \le shift < n$ such that rotating s by shift produces t. This can be done by concatenating s with itself (s + s) and searching for t as a substring. Each occurrence gives a valid shift.
Count Ways for k = 1: If k = 1, the number of valid rotations directly gives the answer.
General Case for k > 1: For k > 1, we use combinatorial reasoning:

Let same be the number of shifts that are 0 modulo n (identity).
Let diff be the number of shifts that are not 0 (non-identity).
Recursively, the number of ways to reach t in k steps is diff * (diff + same)^(k-1). This counts sequences where the first move must be a non-identity shift, and subsequent moves can be any shift.

Modular Arithmetic: Since k is very large, all exponentiation should be done modulo $10^9 + 7$ using fast modular exponentiation.
Return Result: Sum up the valid sequences modulo $10^9 + 7$ and return.

Why it works: The algorithm relies on the cyclic rotation property of the string. By reducing the problem to counting valid rotations and sequences of shifts, we avoid simulating all k operations. Modular exponentiation guarantees correctness for large k.

Python Solution

class Solution:
    MOD = 10**9 + 7
    
    def numberOfWays(self, s: str, t: str, k: int) -> int:
        n = len(s)
        if s == t:
            same = n - 1
            diff = 1
        else:
            # Find the unique rotation distance
            concat = s + s
            idx = concat.find(t)
            if idx == -1 or idx == n:
                return 0
            same = 0
            diff = 1
        
        if k == 1:
            return diff % self.MOD
        
        # Fast modular exponentiation
        def mod_pow(x, y):
            result = 1
            x %= self.MOD
            while y:
                if y % 2:
                    result = result * x % self.MOD
                x = x * x % self.MOD
                y //= 2
            return result
        
        return diff * mod_pow(same + diff, k - 1) % self.MOD

Explanation:

concat.find(t) locates the rotation shift needed to turn s into t.
same counts identity rotations; diff counts non-identity shifts.
mod_pow performs fast modular exponentiation to handle very large k.
The result is computed as diff * (same + diff)^(k-1) modulo $10^9 + 7$.

Go Solution

package main

const MOD int64 = 1e9 + 7

func numberOfWays(s string, t string, k int64) int {
    n := int64(len(s))
    var same, diff int64
    if s == t {
        same = n - 1
        diff = 1
    } else {
        concat := s + s
        idx := int64(-1)
        for i := int64(1); i < n; i++ {
            if concat[i:i+n] == t {
                idx = i
                break
            }
        }
        if idx == -1 {
            return 0
        }
        same = 0
        diff = 1
    }
    
    if k == 1 {
        return int(diff % MOD)
    }
    
    var modPow func(int64, int64) int64
    modPow = func(x, y int64) int64 {
        res := int64(1)
        x %= MOD
        for y > 0 {
            if y%2 == 1 {
                res = res * x % MOD
            }
            x = x * x % MOD
            y /= 2
        }
        return res
    }
    
    return int(diff * modPow(same+diff, k-1) % MOD)
}

Go-specific notes:

Go slices require careful handling of string indices.
Integer overflow is handled by using int64.
Modular exponentiation is the same as in Python.

Worked Examples

Example 1: s = "abcd", t = "cdab", k = 2

Rotation shifts: 2 gives "cdab".
First operation must choose shift 2 or 3 (non-identity).
Second operation can be any shift.
Total ways = 2.

Example 2: s = "ababab", t = "ababab", k = 1

s == t, identity rotations = 5, non-identity = 1.
k = 1, only non-identity moves are counted, so result = 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + log k)	O(n) for rotation check, O(log k) for modular exponentiation
Space	O(n)	O(n) for concatenated string

The algorithm is efficient even for n = 5 * 10^5 and k = 10^15 because it avoids iterating over all k steps.

Test Cases

# test cases
sol = Solution()
assert sol.numberOfWays("abcd", "cdab", 2) == 2  # example 1
assert sol.numberOfWays("ababab", "ababab", 1) == 2  # example 2
assert sol.numberOfWays("aaaa", "aaaa", 3) == 3  # identical letters
assert sol.numberOfWays("