Can Convert String in K Moves
Given two strings s and t, your goal is to convert s into t in k moves or less.
During the i^th (1 <= i <= k) move you can:
- Choose any index
j(1-indexed) froms, such that1 <= j <= s.lengthandjhas not been chosen in any previous move, and shift the character at that indexitimes. - Do nothing.
Shifting a character means replacing it by the next letter in the alphabet, wrapping around so that 'z' becomes 'a'. Shifting a character by i means applying the shift operation i times.
Remember that any index j can be picked at most once.
Return true if it is possible to convert s into t in no more than k moves; otherwise, return false.
Example 1
Input
s = "input", t = "ouput", k = 9Output
trueIn the 6th move, shift
'i' 6 times to get 'o', and in the 7th move shift 'n' to get 'u'.Example 2
Input
s = "abc", t = "bcd", k = 10Output
falseEach character needs one shift, but after using the 1st move for
'a' to 'b', there is no way to shift the other characters by exactly one in the remaining moves.Constraints
- 1 <= s.length, t.length <= 10^5
- 0 <= k <= 10^9
- s, t contain only lowercase English letters.