#2851
String Transformation
international master · 2075 · lc hard +32 · failed · 26.8% accepted · 183 likes · top 5%
Description
Two strings s and t of equal length n and an integer k are given. You may repeatedly apply the following operation on s:
- Remove a suffix of length l (where 0 < l < n) and prepend it to s.
For example, from s = 'abcd', removing suffix 'cd' gives s = 'cdab'.
Return the number of ways to transform s into t in exactly k operations, 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".
Example 2:
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 3:
Input: s = "ababab", t = "ababab", k = 1
Output: 2
Explanation:
First way:
Choose suffix from index = 2, so resulting s = "ababab".
Example 4:
Second way:
Choose suffix from index = 4, so resulting s = "ababab".
Code
1
2
3