String Transformation - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
2851. String Transformation
Hard
50 Points
Math
String
Dynamic Programming
String Matching
You are given two strings s and t of equal length n. You can perform the following operation on the string s:
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.
Examples
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.
2851. String Transformation
Hard
50 Points
Math
String
Dynamic Programming
String Matching
You are given two strings s and t of equal length n. You can perform the following operation on the string s:
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.
Examples
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.