Given two strings&nbsp;s&nbsp;and&nbsp;t, your goal is to convert&nbsp;s&nbsp;into&nbsp;t&nbsp;in&nbsp;k&nbsp;moves or less.

During the&nbsp;ith&nbsp;(1 &lt;= i &lt;= k)&nbsp;move you can:


	Choose any index&nbsp;j&nbsp;(1-indexed) from&nbsp;s, such that&nbsp;1 &lt;= j &lt;= s.length&nbsp;and j&nbsp;has not been chosen in any previous move,&nbsp;and shift the character at that index&nbsp;i&nbsp;times.
	Do nothing.


Shifting a character means replacing it by the next letter in the alphabet&nbsp;(wrapping around so that&nbsp;'z'&nbsp;becomes&nbsp;'a'). Shifting a character by&nbsp;i&nbsp;means applying the shift operations&nbsp;i&nbsp;times.

Remember that any index&nbsp;j&nbsp;can be picked at most once.

Return&nbsp;true&nbsp;if it's possible to convert&nbsp;s&nbsp;into&nbsp;t&nbsp;in no more than&nbsp;k&nbsp;moves, otherwise return&nbsp;false.

&nbsp;
Example 1:

Input: s = "input", t = "ouput", k = 9
Output: true
Explanation: In the 6th move, we shift 'i' 6 times to get 'o'. And in the 7th move we shift 'n' to get 'u'.


Example 2:

Input: s = "abc", t = "bcd", k = 10
Output: false
Explanation: We need to shift each character in s one time to convert it into t. We can shift 'a' to 'b' during the 1st move. However, there is no way to shift the other characters in the remaining moves to obtain t from s.


Example 3:

Input: s = "aab", t = "bbb", k = 27
Output: true
Explanation: In the 1st move, we shift the first 'a' 1 time to get 'b'. In the 27th move, we shift the second 'a' 27 times to get 'b'.


&nbsp;
Constraints:


	1 &lt;= s.length, t.length &lt;= 10^5
	0 &lt;= k &lt;= 10^9
	s, t contain&nbsp;only lowercase English letters.


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False

        cycles, extra = divmod(k, 26)
        shifts = [cycles + (shift <= extra) for shift in range(26)]

        for cs, ct in zip(s, t):
            shift = (ord(ct) - ord(cs)) % 26
            if shift == 0:
                continue
            if not shifts[shift]:
                return False
            shifts[shift] -= 1

        return True
class Solution {
    public boolean canConvertString(String s, String t, int k) {
       //if strings lengths not equal return false
        if(s.length()!=t.length())return false;
       //array to count number of times a difference can repeat
        int b[]=new int[26];
        int h=k/26;
        int h1=k%26;
        //count of each number from 1 to 26 from 1 to k
        for(int i=0;i<26;i++){
            b[i]+=h;
            if(i<=h1)b[i]++;
        }

       int i=0;
        while(i<s.length()){
            //if both characters equal increment i
            if(s.charAt(i)==t.charAt(i)){
                i++;
            }else{
                //else now find difference
                //+26 because we dont know it can be negative also and again mod with 26
                int diff=((t.charAt(i)-s.charAt(i))+26)%26;
                //decrement count after usage of one value of b[diff]
                b[diff]--;
                //if b[diff]<0 means over usage than given so return false
                if(b[diff]<0) return false;
                //else finally increment
                else i++;
            }

        }
        return true;
    }
}
class Solution {
public:
    bool canConvertString(string s, string t, int k) {
        int m = s.length(), n = t.length(), count = 0;
        if (m != n) return false;
        unordered_map<int, int> mp;
        for (int i = 0; i < m; i++) {
            if (t[i] == s[i]) continue;
            int diff = t[i] - s[i] < 0 ? 26 + t[i] - s[i] : t[i] - s[i];
            if (mp.find(diff) == mp.end()) {
                count = max(count, diff);
            } else {
                count = max(count, (mp[diff] * 26) + diff);
            }
            mp[diff]++;
            if (count > k) return false;
        }
        return count <= k;
    }
    
}; 
/**
 * @param {string} s
 * @param {string} t
 * @param {number} k
 * @return {boolean}
 */
 var canConvertString = function(s, t, k) {
    let res = true;
    if(s.length === t.length){
        let tmp = [];
        let countMap = new Map();
        for(let i=0; i<s.length; i++){
            let n1 = s[i].charCodeAt();
            let n2 = t[i].charCodeAt();
            let r = n2 - n1;
            if(r < 0){
                r += 26;
            }
            // exclude special case 0
            if(r > 0){
                // Considering repeated letters, the unrepeated move should change to r + 26*n (n>=0)
                // use hash table to count the same letter
                if(!countMap.has(r)){
                    // first time to move
                    countMap.set(r, 1);
                    tmp.push(r);
                }else{
                    // n time to move, n means the count of the same letter
                    let c = countMap.get(r);
                    tmp.push(r + c * 26);
                    // update count
                    countMap.set(r, c+1);
                }
            }
        }
        // check all possible move in range
        for(let i=0; i<tmp.length; i++){
            let t = tmp[i];
            if(t > k){
                res = false;
                break;
            }
        }
    }else{
        res = false;
    }

    return res;
};
Can Convert String in K Moves