In this guide, you will get 2851. String Transformation LeetCode Solution with the best time and space complexity. The solution to String Transformation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
Complexity Analysis
Time Complexity: O(n + \log k)
Space Complexity: O(n)
2851. String Transformation LeetCode Solution in C++
class Solution {
public:
// This dynamic programming table dp[k][i] represents the number of ways to
// rearrange the string s after k steps such that it starts with s[i].
// A string can be rotated from 1 to n - 1 times. The transition rule is
// dp[k][i] = sum(dp[k - 1][j]) for all j != i. For example, when n = 4 and
// k = 3, the table looks like this:
//
// -----------------------------------------------------------
// | | i = 0 | i = 1 | i = 2 | i = 3 | sum = (n - 1)^k |
// -----------------------------------------------------------
// | k = 0 | 1 | 0 | 0 | 0 | 1 |
// | k = 1 | 0 | 1 | 1 | 1 | 3 |
// | k = 2 | 3 | 2 | 2 | 2 | 9 |
// | k = 3 | 6 | 7 | 7 | 7 | 27 |
// -----------------------------------------------------------
//
// By observation, we have
// * dp[k][!0] = ((n - 1)^k - (-1)^k) / n
// * dp[k][0] = dp[k][!0] + (-1)^k
int numberOfWays(string s, string t, long long k) {
const int n = s.length();
const int negOnePowK = (k % 2 == 0 ? 1 : -1); // (-1)^k
const vector<int> z = zFunction(s + t + t);
const vector<int> indices = getIndices(z, n);
vector<int> dp(2); // dp[0] := dp[k][0]; dp[1] := dp[k][!0]
dp[1] = (modPow(n - 1, k) - negOnePowK + kMod) % kMod *
modPow(n, kMod - 2) % kMod;
dp[0] = (dp[1] + negOnePowK + kMod) % kMod;
return accumulate(indices.begin(), indices.end(), 0L,
[&](long subtotal, int index) {
return (subtotal + dp[index == 0 ? 0 : 1]) % kMod;
});
}
private:
static constexpr int kMod = 1'000'000'007;
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
// Returns the z array, where z[i] is the length of the longest prefix of
// s[i..n) which is also a prefix of s.
//
// https://cp-algorithms.com/string/z-function.html#implementation
vector<int> zFunction(const string& s) {
const int n = s.length();
vector<int> z(n);
int l = 0;
int r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
// Returns the indices in `s` s.t. for each `i` in the returned indices,
// `s[i..n) + s[0..i) = t`.
vector<int> getIndices(const vector<int>& z, int n) {
vector<int> indices;
for (int i = n; i < n + n; ++i)
if (z[i] >= n)
indices.push_back(i - n);
return indices;
}
}; /* code provided by PROGIEZ */
2851. String Transformation LeetCode Solution in Java
class Solution {
// This dynamic programming table dp[k][i] represents the number of ways to
// rearrange the String s after k steps such that it starts with s[i].
// A String can be rotated from 1 to n - 1 times. The transition rule is
// dp[k][i] = sum(dp[k - 1][j]) for all j != i. For example, when n = 4 and
// k = 3, the table looks like this:
//
// -----------------------------------------------------------
// | | i = 0 | i = 1 | i = 2 | i = 3 | sum = (n - 1)^k |
// -----------------------------------------------------------
// | k = 0 | 1 | 0 | 0 | 0 | 1 |
// | k = 1 | 0 | 1 | 1 | 1 | 3 |
// | k = 2 | 3 | 2 | 2 | 2 | 9 |
// | k = 3 | 6 | 7 | 7 | 7 | 27 |
// -----------------------------------------------------------
//
// By observation, we have
// * dp[k][!0] = ((n - 1)^k - (-1)^k) / n
// * dp[k][0] = dp[k][!0] + (-1)^k
public int numberOfWays(String s, String t, long k) {
final int n = s.length();
final int negOnePowK = (k % 2 == 0 ? 1 : -1); // (-1)^k
final int[] z = zFunction(s + t + t);
final List<Integer> indices = getIndices(z, n);
int[] dp = new int[2]; // dp[0] := dp[k][0]; dp[1] := dp[k][!0]
dp[1] = (int) ((modPow(n - 1, k) - negOnePowK + kMod) % kMod * modPow(n, kMod - 2) % kMod);
dp[0] = (int) ((dp[1] + negOnePowK + kMod) % kMod);
int ans = 0;
for (final int index : getIndices(z, n)) {
ans += dp[index == 0 ? 0 : 1];
ans %= kMod;
}
return ans;
}
private static final int kMod = 1_000_000_007;
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
// Returns the z array, where z[i] is the length of the longest prefix of
// s[i..n) which is also a prefix of s.
//
// https://cp-algorithms.com/string/z-function.html#implementation
private int[] zFunction(final String s) {
final int n = s.length();
int[] z = new int[n];
int l = 0;
int r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i]))
++z[i];
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
// Returns the indices in `s` s.t. for each `i` in the returned indices,
// `s[i..n) + s[0..i) = t`.
private List<Integer> getIndices(int[] z, int n) {
List<Integer> indices = new ArrayList<>();
for (int i = n; i < n + n; ++i)
if (z[i] >= n)
indices.add(i - n);
return indices;
}
} // code provided by PROGIEZ
2851. String Transformation LeetCode Solution in Python
class Solution:
# This dynamic programming table dp[k][i] represents the number of ways to
# rearrange the String s after k steps such that it starts with s[i].
# A String can be rotated from 1 to n - 1 times. The transition rule is
# dp[k][i] = sum(dp[k - 1][j]) for all j != i. For example, when n = 4 and
# k = 3, the table looks like this:
#
# -----------------------------------------------------------
# | | i = 0 | i = 1 | i = 2 | i = 3 | sum = (n - 1)^k |
# -----------------------------------------------------------
# | k = 0 | 1 | 0 | 0 | 0 | 1 |
# | k = 1 | 0 | 1 | 1 | 1 | 3 |
# | k = 2 | 3 | 2 | 2 | 2 | 9 |
# | k = 3 | 6 | 7 | 7 | 7 | 27 |
# -----------------------------------------------------------
#
# By observation, we have
# * dp[k][!0] = ((n - 1)^k - (-1)^k) / n
# * dp[k][0] = dp[k][!0] + (-1)^k
def numberOfWays(self, s: str, t: str, k: int) -> int:
kMod = 1_000_000_007
n = len(s)
negOnePowK = 1 if k % 2 == 0 else -1 # (-1)^k
z = self._zFunction(s + t + t)
# indices in `s` s.t. for each `i` in the returned indices,
# `s[i..n) + s[0..i) = t`.
indices = [i - n for i in range(n, n + n) if z[i] >= n]
dp = [0] * 2 # dp[0] := dp[k][0]; dp[1] := dp[k][!0]
dp[1] = (pow(n - 1, k, kMod) - negOnePowK) * pow(n, kMod - 2, kMod)
dp[0] = dp[1] + negOnePowK
return sum(dp[0] if index == 0 else dp[1] for index in indices) % kMod
def _zFunction(self, s: str) -> list[int]:
"""
Returns the z array, where z[i] is the length of the longest prefix of
s[i..n) which is also a prefix of s.
https://cp-algorithms.com/string/z-function.html#implementation
"""
n = len(s)
z = [0] * n
l = 0
r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l = i
r = i + z[i]
return z # code by PROGIEZ
