2851. String Transformation Hard

1/**
2 * [2851] String Transformation
3 *
4 * You are given two strings s and t of equal length n. You can perform the following operation on the string s:
5 * 
6 * 	Remove a suffix of s of length l where 0 < l < n and append it at the start of s.<br />
7 * 	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'.
8 * 
9 * You are also given an integer k. Return the number of ways in which s can be transformed into t in exactly k operations.
10 * Since the answer can be large, return it modulo 10^9 + 7.
11 *  
12 * <strong class="example">Example 1:
13 * 
14 * Input: s = "abcd", t = "cdab", k = 2
15 * Output: 2
16 * Explanation: 
17 * First way:
18 * In first operation, choose suffix from index = 3, so resulting s = "dabc".
19 * In second operation, choose suffix from index = 3, so resulting s = "cdab".
20 * Second way:
21 * In first operation, choose suffix from index = 1, so resulting s = "bcda".
22 * In second operation, choose suffix from index = 1, so resulting s = "cdab".
23 * 
24 * <strong class="example">Example 2:
25 * 
26 * Input: s = "ababab", t = "ababab", k = 1
27 * Output: 2
28 * Explanation: 
29 * First way:
30 * Choose suffix from index = 2, so resulting s = "ababab".
31 * Second way:
32 * Choose suffix from index = 4, so resulting s = "ababab".
33 * 
34 *  
35 * Constraints:
36 * 
37 * 	2 <= s.length <= 5 * 10^5
38 * 	1 <= k <= 10^15
39 * 	s.length == t.length
40 * 	s and t consist of only lowercase English alphabets.
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/string-transformation/
46// discuss: https://leetcode.com/problems/string-transformation/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn number_of_ways(s: String, t: String, k: i64) -> i32 {
52        0
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_2851() {
64    }
65}
66