Given two strings s and t, your goal is to convert s into t in k moves or less.
During the ith (1 <= i <= k) move you can:

Choose any index j (1-indexed) from s, such that 1 <= j <= s.length and j has not been chosen in any previous move, and shift the character at that index i times.
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 operations i times.
Remember that any index j can be picked at most once.
Return true if it's possible to convert s into t in no more than k moves, otherwise return false.
 
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'.

 
Constraints:

1 <= s.length, t.length <= 10^5
0 <= k <= 10^9
s, t contain only lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        

Solutions:
class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        c = Counter((ord(c2) - ord(c1)) % 26 for c1, c2 in zip(s, t))
        return k >= max(
            (m + 26 * (count - 1) for m, count in list(c.items()) if m),
            default = 0)


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        c = Counter((ord(c2) - ord(c1)) % 26 for c1, c2 in zip(s, t))
        return k >= max((m + 26 * (count - 1) for m, count in list(c.items()) if m),
                        default = 0)


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        count = [0 for _ in range(26)]
        for a, b in zip(s, t):
            if a == b:
                continue
            shift = (ord(b) - ord(a)) % 26
            count[shift] += 1
        max_shift = 0
        max_count = 0
        for i in range(25, -1, -1):
            if count[i] > max_count:
                max_shift = i
                max_count = count[i]
        if max_count < 1:
            return True
        # print('max_count', max_count, 'max_shift', max_shift)
        return (((max_count - 1) * 26) + max_shift) <= k

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        if len(s) != len(t):
            return False
        
        cnts = [0]*26
        for char_s, char_t in zip(s, t):
            if char_s == char_t:
                continue
            elif char_s < char_t:
                moves_req = ord(char_t) - ord(char_s)
            else:
                moves_req = 26 - ord(char_s) + ord(char_t)
                
            cnts[moves_req] += 1
            if moves_req > k or cnts[moves_req]-1 > ((k-moves_req)/26):
                return False
        return True
            


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t): return False
        dic = {}
        for a, b in zip(s, t):
            gap = ord(b) - ord(a)
            single = gap if gap >= 0 else 26 + gap
            if single == 0: continue
            if single not in dic:
                dic[single] = 0
            else:
                dic[single] += 1
            # print(a, b, \" dic:\", dic)
            if dic[single] * 26 + single > k: return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        if len(s) != len(t):
            return False
        
        diff = defaultdict(int)
        for sc, tc in zip(s, t):
            d = (ord(tc) - ord(sc)) % 26
            if d == 0: continue
            if d > k: return False
            diff[d] += 1
            if ((diff[d] - 1) * 26) + d > k:
                return False
        
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        count = {}
        total = [0]
        # print(count)
        for i in range(len(s)):
            if ord(s[i]) > ord(t[i]):
                # print('case {} {}'.format(s[i], t[i]))
                x = 122 - ord(s[i]) + ord(t[i]) - 96
            else:
                x = ord(t[i]) - ord(s[i])
            # print(\"({} {})\".format(x,i))
            if x != 0:
                if x not in count:
                    count[x] = 0
                if count[x] * 26 + x:
                    max = count[x] * 26 + x
                    if max > k:
                        return False
                count[x] += 1
        # print(max(total))
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        d = {}
        m1 = [0, 0]
        n = len(s)
        if len(t) != n:
            return False
        for i in range(n):
            diff = (ord(t[i])-ord(s[i])) % 26
            if diff != 0:
                if diff not in d:
                    d[diff] = 0
                d[diff]+=1
                m1 = max(m1, [d[diff], diff])
        m2 = 26*(m1[0]-1)+m1[1]
       # print(m2)
        return k >= m2
             
                
                   


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        diff = []
        res = []
        diff.extend(ord(t[i]) - ord(s[i]) + [0, 26][ord(t[i]) < ord(s[i])]
            for i in range(len(s)) if s[i] != t[i])
        counter = Counter(diff)
        res.extend(key + 26*i for key in counter for i in range(counter[key]))
        return all([r <= k  for r in res])
        
                                                
                                            


# 1540. Can Convert String in K Moves

ALPHABET_SIZE = 26

def compute_shift (c1, c2):
    return (ord (c2) - ord (c1)) % ALPHABET_SIZE

def last_shift (shift, frequency):
    return shift + (frequency - 1) * ALPHABET_SIZE

def can_convert_string (s, t, k):
    if len(s) != len(t): return False
    shifts = {}
    for c1, c2 in zip (s, t):
        if c1 != c2:
            shift = compute_shift (c1, c2)
            shifts.setdefault (shift, 0)
            shifts[shift] += 1

    return all (last_shift (shift, frequency) <= k for (shift, frequency) in shifts.items ())

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        return can_convert_string(s, t, k)

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        d = {x: 0 for x in range(1, 26)}
        for cs, ct in zip(s, t):
            diff = (ord(ct) - ord(cs) + 26) % 26
            if diff == 0:
                continue
            nxt = d[diff] * 26 + diff
            if nxt <= k:
                d[diff] += 1
            else:
                return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        count = [0 for _ in range(26)]
        for a, b in zip(s, t):
            if a == b:
                continue
            shift = (ord(b) - ord(a)) % 26
            count[shift] += 1
        ch = ord('z') - ord('a')
        m = count[ch]
        for i in range(24, -1, -1):
            if count[i] > m:
                ch = i
                m = count[i]
        return (m - 1) * 26 + ch <= k

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        dic = {}    
        ans = []
        for i in range(len(s)):
            if s[i] == t[i]:
                continue
            diff = ord(t[i]) - ord(s[i]) + (0, 26)[ord(t[i]) < ord(s[i])]
            dic[diff] = dic.get(diff, 0) + 1
            if (diff + 26*(dic[diff] - 1)) > k:
                return False
        return True
            
            
                                            


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        if len(s) != len(t):
            return False
        
        
        shift_times = []
        for idx in range(len(s)):
            a = s[idx]
            b = t[idx]
            if ord(a) <= ord(b):
                shift_times.append(ord(b) - ord(a))
            else:
                shift_times.append( (ord('z')-ord(a))+(ord(b)-ord('a')) + 1 )
            #print(shift_times, b, a, (ord('z')-ord(b)), (ord(a)-ord('a')))
            ## pruning for unable to shift
            if shift_times[-1] > k:
                return False
        

        shift_used = dict()
        for idx in range(len(shift_times)):
            shift_amount = shift_times[idx]
            if shift_amount == 0:
                continue
            ## shift_times already used before, should plus wrapping
            if shift_amount in shift_used:
                if 26 * shift_used[shift_amount] + shift_amount > k:
                    return False
                else:
                    shift_used[shift_amount] += 1
            ## can shift normally
            else:
                shift_used[shift_amount] = 1
        return True
        


def shift(c, n):
    return chr(ord(c) + n%26)

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        d = {}
        mx = 0
        for i in range(len(s)):
            c1 = s[i]
            c2 = t[i]
            if c1 == c2:
                continue
            j = ord(c2) - ord(c1)
            j = j % 26
            if j not in d:
                d[j] = 1
            else:
                d[j] += 1
            mx = max(mx, (d[j]-1)*26+j)
        return mx <= k

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        shifts = []
        for ch1, ch2 in zip(s, t):
            asc1 = ord(ch1) - ord('a')
            asc2 = ord(ch2) - ord('a')
            diff = asc2 - asc1 if asc2 >= asc1 else 26 - asc1 + asc2
            assert diff >= 0
            if diff > 0:
                shifts.append(diff)
        
        shifts.sort()
    
        most = 0
        freq = defaultdict(int)
        for s in shifts:
            most = max(most, s + freq[s] * 26)
            freq[s] += 1
        return most <= k

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        if len(s) != len(t):
            return False
        
        rotations, extra = divmod(k, 26)
        
        diff = []
        
        for index in range(len(s)):
            difference = ord(t[index]) - ord(s[index])
            if difference:
                diff.append(difference)
        
        dictionary = dict()
        
        for number in range(1,26):
            dictionary[number] = rotations
            
            if number <= extra:
                dictionary[number]+= 1
        
        if not diff:
            return True
        
        for d in diff:
            
            if d < 0:
                net_d = d+26
                if dictionary[net_d]:
                    dictionary[net_d] -= 1
                
                else:
                    return False
            
            else:
                if dictionary[d]:
                    dictionary[d] -= 1
                
                else:
                    return False
        
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        seen = {i: i for i in range(1, 27)}
        for i in range(len(s)):
            ch1, ch2 = s[i], t[i]
            if ch1 == ch2:
                continue
            else:
                move = ord(ch2) - ord(ch1) + 26 * (ord(ch1) > ord(ch2))
                last = seen[move]
                if last > k:
                    return False
                else:
                    seen[move] = last + 26
                
        
        return True
                



import string

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t): return False
        
        mod=k%26
        div = k//26
        def f(sh):
            l = 1 if sh < mod else 0
            return div + l
        
        shifts=[0 for i in range(26)]
        for l1, l2 in zip(s, t):
            if l1 == l2: continue
            sh = string.ascii_lowercase.index(l2)-string.ascii_lowercase.index(l1)
            sh = sh if sh >=0 else sh+26
            shifts[sh-1]+=1
            if shifts[sh-1] > f(sh-1): return False
                     
        return True
            
            
            


from collections import defaultdict

class Solution:
  def canConvertString(self, s: str, t: str, n: int) -> bool:
    if len(s) != len(t):
      return False
    
    d = defaultdict(int)
    for c1, c2 in zip(s, t):
      v = (26 + ord(c2) - ord(c1)) % 26
      if v:
        d[v] += 1
        
    
    for k, v in list(d.items()):
      if k + 26 * (v - 1) > n:
        return False
    
    return True
        


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        numMoves = [int(k / 26)] * 26
        for i in range(1, (k % 26) + 1):
            numMoves[i] += 1
        
        for i in range(len(t)):
            shift = (ord(t[i]) - ord(s[i])) % 26
            if shift == 0:
                continue
            numMoves[shift] -= 1
            if numMoves[shift] < 0:
                return False
        
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s)!=len(t):
            return False
        h=[0]*27
        for i in range(len(s)):
            c=ord(t[i])-ord(s[i])
            if c==0:
                continue
            if c<0:
                c+=26
            h[c]+=1
            
        for i in range(1,len(h)):
            if i + (h[i] - 1) * 26 > k: 
                return False;
            
        return True            


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0 for i in range(26)]
        for a,b in zip(s,t):
            cnt[(ord(b) - ord(a)) % 26]+=1
        for i in range(1, 26):
            if cnt[i]  > 0 and (cnt[i] -1) * 26 + i > k:
                return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t) :
            return False
        count = [0] * 26
        seen = set()
        
        for cs, ct in zip(s, t):
            diff = (ord(ct) - ord(cs)) % 26
            if diff != 0:
                if diff in seen:
                    count[diff] += 26
                    if count[diff] > k:
                        return False
                else:
                    count[diff] = diff
                    if diff > k:
                        return False
                    seen.add(diff)
        return True
        # alpha = '0abcdefghijklmnopqrstuvwxyz'
        # aplha_d = {}
        # val = 1
        # for i in range(len(aplha)):
        #     aplha_d[aplha[i]]


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s)!=len(t):
            return False
        d=defaultdict(int)
        for i in range(len(s)):
            #l.append((ord(t[i])-ord(s[i]))%26)
            n=(ord(t[i])-ord(s[i]))%26
            if n>0:
                d[n]+=1
            
        d2=defaultdict(int)
        kk=k//26
        for i in range(26):
            d2[i+1]=kk
        for i in range(k%26):
            d2[i+1]+=1
        #print(d,d2)
        for k in d:
            if k not in d2 or d[k]>d2[k]:
                return False
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        taken = [i for i in range(0, 26)]
        for c1, c2 in zip(s, t):
            g = (ord(c2)-ord(c1)) % 26
            if g == 0:
                continue
            if taken[g] > k:
                return False
            taken[g] += 26
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s)!=len(t):
            return False
        N=26
        cnt=[0]*N
        for i in range(len(s)):
            if s[i]==t[i]:
                continue
            cnt[(ord(t[i])-ord(s[i]))%N]+=1
        # print(cnt)
        for i in range(1,N):
            if cnt[i]>(k//N)+(k%N >=i):
                return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0] * 26
        for cs, ct in zip(s, t):
            diff = (ord(ct) - ord(cs)) % 26
            if diff > 0 and cnt[diff] * 26 + diff > k:
                return False
            cnt[diff] += 1
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        b = k // 26
        budget = {i: b + (i <= (k % 26)) for i in range(1, 26)}
        
        for i, j in zip(s, t):
            shift = (ord(j) - ord(i)) % 26
            if i != j:
                if shift > k:
                    return False
                if budget[shift] == 0:
                    return False
                else:
                    budget[shift] -= 1
                
        return True
            
            
            


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if not len(s)==len(t): return False
        
        n = len(s)
        count = defaultdict(int)
        for i in range(n):
            if s[i]!=t[i]:
                temp = -ord(t[i])+ord(s[i])
                count[ (temp+26)%26 ] += 1
            
        k1,k2 = k//26,k%26
        helper = defaultdict(int)
        for i in range(1,26):
            helper[i] += k1

        if k2:
            for i in range(1,k2+1):
                helper[26-i] += 1
                    
        print(count)
        print(helper)
        
        for i in count:
            if not (i in helper) or helper[i]<count[i]:
                return False
        return True

class Solution:
    # https://leetcode.com/problems/can-convert-string-in-k-moves/discuss/826856/c%2B%2B-simple-sol...using-maps
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        lookup = collections.defaultdict(int)
        for i in range(len(s)):
            if s[i] != t[i]:
                diff = (ord(t[i]) - ord(s[i]) + 26) % 26 
                if diff > k:
                    return False
                lookup[diff] += 1
        
        for diff, freq in list(lookup.items()):
            maxCount = (freq - 1) * 26 + diff
            if maxCount > k:
                return False
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        times = {}
        if (len(s) != len(t)): return False
        for i in range(len(s)):
            orig = (ord(t[i])-ord(s[i])+26)%26
            totry = orig
            if totry == 0: continue
            if orig in times:
                totry = times[orig]
                totry += 26
            if totry > k:
                return False
            times[orig] = totry
        return True

class Solution:
    def canConvertString(self, s, t, k):
        n, m = len(s), len(t)
        if n != m:
            return False
        cnt = [0] * 26
        for i in range(n):
            if s[i] == t[i]:
                continue
            diff = (ord(t[i]) - ord(s[i])) % 26
            if cnt[diff] * 26 + diff > k:
                return False
            cnt[diff] += 1
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        shifts = [0 for x in range(1, 27)]
        
        for i in range(len(s)):
            if t[i] == s[i]:
                continue
            diff = (ord(t[i]) - ord(s[i])) % 26
            
            if ((shifts[diff]) * 26 + diff) > k:
                return False
            shifts[diff] += 1
        
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        if len(s) != len(t):
            return False
        
        dd = collections.defaultdict(int)
        
        for i,v in zip(s,t):
            diff = (ord(v) - ord(i)) % 26 
            if diff > 0 and diff + dd[diff] * 26 > k:
                return False
            dd[diff] += 1
        
        return True

import collections
class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        # check lengths
        n1 = len(s)
        n2 = len(t)
        if n1 != n2:
            return False
        n = n1
        
        # find diffArray
        diffArray = [(ord(t[i])-ord(s[i]))%26 for i in range(n)]
       
        # frequency of difference
        cda = collections.Counter(diffArray)
        
        # delete 0
        del cda[0]
        
        minK = 0
        if len(cda) > 0 :
            key = max([(i[1], i[0])for i in list(cda.items())])
            #print(key)
            minK = (key[0] - 1) *26 + key[1]
        return k >= minK



class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0] * 26
        for cs, ct in zip(s, t):
            diff = (ord(ct) - ord(cs)) % 26
            if diff > 0 and cnt[diff] * 26 + diff > k:
                return False
            cnt[diff] += 1
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t): return False
        
        moves = collections.Counter()
        
        for si, ti in zip(s, t):
            shifts = (ord(ti) - ord(si)) % 26
            moves[shifts] += 1
        
        for i in range(1, 26):
            total_moves = moves[i]
            
            if i + 26*(total_moves-1) > k: return False
        
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        jumps=list(range(26))
        if len(s)!=len(t):
            return False
        for i in range(len(s)):
            if s[i]==t[i]:
                continue
            jump=(ord(t[i])-ord(s[i])+26)%26
            if jumps[jump]>k:
                return False
            jumps[jump]+=26
        return True

from collections import Counter 
class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0] * 26
        for cs, ct in zip(s, t):
            diff = (ord(ct) - ord(cs)) % 26
            if diff > 0 and cnt[diff] * 26 + diff > k:
                return False
            cnt[diff] += 1
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        n1, n2 = len(s), len(t)
        if n1 != n2:
            return False
        if k == 0:
            return s == t
        
        # record how many letters need to be changed, autobump step if step is found 
        steps = collections.defaultdict(int)
        for sc, tc in zip(s, t):
            if sc != tc:
                idx_t = ord(tc)
                idx_s = ord(sc)
                if idx_s < idx_t:
                    step = idx_t - idx_s
                else:
                    step = idx_t - idx_s + 26
               
                if step > k:
                    return False
                steps[step] += 1
                
                
        for step in steps:
            if (steps[step] - 1) * 26 + step > k:
                return False
          

        return True
                    
        


def dist(s_c, t_c):
    if s_c == t_c:
        return 0
    elif s_c < t_c:
        return ord(t_c) - ord(s_c)
    else: # s_c > t_c
        return ord('z') - ord(s_c) + ord(t_c) - ord('a') + 1

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        distances = [0] * 26
        if len(s) != len(t):
            return False
        for s_c, t_c in zip(s, t):
            d = dist(s_c, t_c)
            if d != 0:
                distances[d] += 1
        for i, d in enumerate(distances):
            if d > 0:
                if (d - 1) * 26 + i > k:
                    return False
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        o = {}
        if len(s) != len(t):return False
        for i in range(len(s)):
            l = (ord(t[i]) -  ord(s[i]))%26
            if l == 0:continue
            if l > k :return False
            if l not in o :
                o[l] = l
            else:
                last = o[l]
                if last + 26 > k: return False
                o[l] = 26 + last
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        distance = Counter((ord(b) - ord(a)) % 26 for a, b in zip(s, t) if a != b)
        maxf = [-1, -1]
        for c, f in distance.items():
            if f > maxf[1] or f == maxf[1] and c > maxf[0]:
                maxf[0] = c
                maxf[1] = f
        return not distance or ((maxf[1] - 1) * 26 + maxf[0]) <= k

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        if len(s) != len(t):
            return False
        
        cnts = [0]*26
        for s_char, t_char in zip(s, t):
            if s_char == t_char:
                continue
            elif s_char > t_char:
                moves_req = 26 - (ord(s_char)-ord(t_char))
            else:
                moves_req = ord(t_char) - ord(s_char)
            
            cnts[moves_req] += 1
            if moves_req > k or cnts[moves_req] > (k-moves_req)//26+1:
                return False
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if(len(s) != len(t)):
            return False
        idx_dict = [0] * 26
        # for i in range(1, 26):
        #     idx_dict[i] = 0
        
        for idx, sc in enumerate(s):
            tc = t[idx]
            
            if(sc == tc):
                # idx_list.append(0)
                continue
            
            sasc = ord(sc)
            tasc = ord(tc)
            
            if(sasc < tasc):
                movei = tasc - sasc
            else:
                movei = 26 - sasc + tasc
            # while(movei in idx_set):
            #         movei = movei + 26
            origini = movei
            movei = movei + 26 * idx_dict[movei]
            idx_dict[origini] += 1
            if(movei > k):
                return False
            # idx_list.append(movei)
            # idx_set.add(movei)
        #print(idx_list)
        return True


def no_of_shifts_away(a, b):
    return (ord(b) - ord(a)) % 26


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        in1_len = len(s)
        in2_len = len(t)
        max_duplicates_in_shift = []
        for i in range(26):
            max_duplicates_in_shift.append(max(0, 1 + ((k - i) // 26)))
        if in1_len != in2_len:
            return False
        for i in range(in1_len):
            shifts_required = no_of_shifts_away(s[i], t[i])
            if shifts_required > k:
                return False
            if shifts_required != 0:
                max_duplicates_in_shift[shifts_required] -= 1
                if max_duplicates_in_shift[shifts_required] < 0:
                    return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        change = []
        if len(s)!=len(t):
            return False
        for a,b in zip(s,t):
            if a!=b:
                change.append(ord(b)-ord(a))
        for index,number in enumerate(change):
            if number < 0:
                change[index]+=26
        count = [0]*26
        for index,number in enumerate(count):
            count[index]+=int(k/26)
        remaining = k%26
        i=1
        for j in range(remaining):
            count[i]+=1
            i+=1
        for number in change:
            if count[number]==0:
                return False
            else:
                count[number]-=1
        return True
            


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        a = [k // 26 for _ in range(27)]
        
        for i in range(k % 26 + 1):
            a[i] += 1
        
        ns, nt = len(s), len(t)
        if ns != nt: return False
        
        for i in range(ns):
            if s[i] == t[i]:
                continue
            else:
                d = ord(t[i]) - ord(s[i]) if t[i] > s[i] else ord(t[i]) + 26 - ord(s[i])
                if a[d] <= 0:
                    return False
                a[d] -= 1
        
        return True
                    
        


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        moves = defaultdict(lambda: 0) 
        K_div = k // 26
        K_mod = k % 26
        
        if len(s) != len(t):
            return False
        
        for cs, ct in zip(s, t):
            ordc = ord(cs)
            ordt = ord(ct)
            
            move = ordt - ordc 
            if move < 0:
                move += 26
            
            if move == 0:
                continue
                
            numMoves = K_div + (1 if move <= K_mod else 0) 
            
            if moves[move] == numMoves:
                return False
            
            moves[move] += 1
            
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        l = [0] * 26
        for i in range(len(s)):
            if s[i] == t[i]:
                continue
            x = (ord(t[i]) - ord(s[i]) + 26) % 26
            if l[x] * 26 + x > k:
                return False
            l[x] += 1
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if(s==t):
            return True
        if(len(s)!=len(t)):
            return False
        has={}
        for i in range(1,27):
            num=26+i
            if(i<=k):
                has[i]=1
                x=(k-i)//26
                has[i]+=x
        n=len(s)
        print(has)
       
        count=0
        for i in range(n):
            if(s[i]==t[i]):
                count+=1
                continue
            diff=(ord(t[i])-ord(s[i]))%26

            if(diff in has):
                count+=1
                has[diff]-=1
                if(has[diff]==0):
                    del has[diff]
            else:
                return False
        # print(has2)
        if(count==n):
            return True
        return False
                
            
            
            
            


class Solution:
    
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        n = len(s)
        m = len(t)
        
        if m!=n:
            return False
        
        if s==t:
            return True
        
        shift = {}
        
        shift[0] = 0
        
        for i in range(n):
            move = (ord(t[i])-ord(s[i]))%26

            if move>0:
                
                if move in shift:
                    new_move = 26*shift[move] + move
                    shift[move] = shift[move] + 1
                    move = new_move
                
                else:
                    shift[move] = 1
                
                if move>k:
                    return False
            
            else:
                shift[0] = shift[0] + 1
        
        return True
                
            
            


import collections
class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        # check lengths
        n1 = len(s)
        n2 = len(t)
        if n1 != n2:
            return False
        n = n1
        
        # find diffArray
        diffArray = [(ord(t[i])-ord(s[i]))%26 for i in range(n)]
       
        # frequency of difference
        cda = collections.Counter(diffArray)
        print(cda)
        
        # delete 0
        del cda[0]
        elements = sorted(list(cda.items()), key=lambda x: (x[1], x[0]), reverse=True)
        minK = 0
        try:
            key = elements[0]
            minK = (key[1] - 1) *26 + key[0]
        except IndexError:
            pass
        print(minK)
        return k >= minK
    


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return 0
        aux = dict()
        for i in range(len(s)):
            if s[i] != t[i]:
                val1, val2 = ord(s[i]), ord(t[i])
                if val1 < val2:
                    if val2 - val1 in aux:
                        aux[val2 - val1] += 1
                    else:   aux[val2 - val1] = 1
                else:
                    if 26 - val1 + val2 in aux:
                        aux[26 - val1 + val2] += 1
                    else:   aux[26 - val1 + val2] = 1
        ans = 0
        for elem in aux:
            ans = max(ans, 26 * (aux[elem]-1) + elem)
        return ans <= k
        
                


class Solution:
     def canConvertString(self, s: str, t: str, k: int) -> bool:        
        if len(s) != len(t):
            return False 
        
        used = {}
        for i in range(len(s)):
            diff = ord(s[i]) - ord(t[i])
            if diff == 0:
                continue 

            i = (26-diff) if diff > 0 else abs(diff)
            if i > k: 
                return False 
            
            if i not in used:
                used[i] = 1
            else:
                move = used[i] * 26 + i
                if move > k:
                    return False 
                else:
                    used[i] += 1 
                
        return True
            
            
        
       


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        # a, b
        if len(s) != len(t):
            return False
        largest = [0]*26
        for i in range(len(s)):
            diff = ord(t[i]) - ord(s[i])
            if diff == 0:
                continue
            elif diff < 0:
                diff += 26
            if largest[diff-1] == 0:
                largest[diff-1] = diff
            else:
                largest[diff-1] += 26
            if largest[diff-1] > k:
                return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        
        if len(s) != len(t):
            return False
        
        d = defaultdict(int)
        
        for sc, tc in zip(s,t):
            
            diff = ( ord(tc) - ord(sc) ) % 26
            
            if diff == 0:
                continue
            
            if diff > k:
                return False
            
            d[diff] += 1
            
            if ((d[diff] - 1) * 26) + diff > k:
                return False
            
        
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        maps = {} # or maybe use array
        for i in range(len(s)):
            if s[i] != t[i]:
                diff = (ord(t[i]) - ord(s[i]) ) % 26
                if diff not in list(maps.keys()):
                    maps[diff] = 1
                else:
                    maps[diff] += 1
                if ((maps[diff] - 1) * 26 + diff) > k:
                    return False
        return True
                
        


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        alreadySeen = {}
        
        for i in range(len(s)):
            if s[i] != t[i]:
                difference = (ord(t[i]) - ord(s[i])) % 26
                
                if difference > k:
                    return False
                
                if difference not in alreadySeen:
                    alreadySeen[difference] = 1
                else:
                    newDifference = difference + alreadySeen[difference] * 26

                    if newDifference > k:
                        return False
                    else:
                        alreadySeen[difference] += 1
        
        return True


class Solution:
    def dist(self, a,b):
        return (ord(b)-ord(a)) % 26
    
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t): 
            return False
        seen = {}
        for x, y in zip(s, t):
            if x == y: 
                continue
            d = self.dist(x,y)            
            if d  > k: 
                return False
            if d not in seen: 
                seen[d] = d
            else:
                last = seen[d]
                if last + 26 > k: 
                    return False
                seen[d] = last + 26
        return True


from collections import Counter


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        ans = Counter()
        for i in range(len(s)):
            key = (ord(t[i]) - ord(s[i])) % 26
            if key != 0 and ans[key] * 26 + key > k:
                return False
            ans[key] += 1
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        cnt = collections.defaultdict(int)
        for i in range(len(s)):
            if s[i] == t[i]:
                continue
            
            shift = 0
            if ord(t[i]) < ord(s[i]):
                shift = ord(t[i]) - ord(s[i]) + 26
            else:
                shift = ord(t[i]) - ord(s[i])
            
            cnt[shift] += 1
        
        for r in cnt:
            # We have cnt[r] letters in s that will need to be shifted r letters to line up with t.
            # We then simply need to check that k is large enough so that there are enough instances
            # of i, 1 <= i <= k, such that i % 26 == r.
            # How do we check? Well if x * 26 + r <= k, then we have (0*26 + r) % 26 == r,
            # (1*26 + r) % 26 == r, (2*26 + r) % 26 == r, ..., (x*26 + r) % 26 == r, i.e there are x + 1 
            # instances of i such that i % 26 == r.
            # Given cnt[r] letters that need to be shifted, we only need to make sure that:
            #   (cnt[r]-1)*26 +r <= k
            #
            if (cnt[r] - 1) * 26 + r > k:
                return False
        return True


def no_of_shifts_away(a, b):
    return (ord(b) - ord(a)) % 26


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        in1_len = len(s)
        freq = {}
        in2_len = len(t)
        max_duplicates_in_shift = []
        for i in range(26):
            max_duplicates_in_shift.append(max(0, 1 + ((k - i) // 26)))
        if in1_len != in2_len:
            return False
        for i in range(in1_len):
            shifts_required = no_of_shifts_away(s[i], t[i])
            if shifts_required > k:
                return False
            if shifts_required != 0:
                if shifts_required in freq:
                    freq[shifts_required] += 1
                    if freq[shifts_required] > max_duplicates_in_shift[shifts_required]:
                        return False
                else:
                    freq[shifts_required] = 1
        return True

class Solution:
    
    
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        

        if len(s) != len(t):
            return False
        
        d = {}
        
        
        for i in range(len(s)):
            
            if s[i] == t[i]:
                continue
                
            diff = (ord(t[i]) - ord(s[i])) % 26
            
            if diff not in d:                
                d[diff] = 1
            else:
                d[diff] += 1
            
            
                
            if (26 * (d[diff]-1)) + diff > k:
                return False
        
        
        return True

class Solution:
    def getMoves(self, cFrom, cTo):
        return (ord(cTo) - ord(cFrom)) % 26 
    
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        usedDict = {}
        
        for cFrom, cTo in zip(s, t):
            if cFrom == cTo:
                continue
            
            moves = self.getMoves(cFrom, cTo)
            
            if moves > k:
                return False
            
            if moves not in usedDict:
                usedDict[moves] = 1
            else:
                if moves + (26 * usedDict[moves]) <= k:
                    usedDict[moves] += 1
                else:
                    return False
                
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t): return False
        
        isUsed = dict()
        for i in range(len(s)):
            ch1, ch2 = ord(s[i]), ord(t[i])
            if ch1 < ch2:
                shift = ch2-ch1
            elif ch1 > ch2:
                shift = 26-(ch1-ch2)
            else:
                continue
                
            initShift = shift
            while 1 <= shift <= k:
                
                if shift not in isUsed:
                    isUsed[initShift] = shift
                    break
                shift = isUsed[initShift]+26
                
            else:
                return False
            
        return True
        


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t): return False #edge case 
        
        visited = {}
        for ss, tt in zip(s, t):
            if ss != tt: 
                d = (ord(tt) - ord(ss)) % 26 #distance 
                if d not in visited: 
                    visited[d] = d
                else: 
                    visited[d] += 26 
                if visited[d] > k: 
                    return False 
        return True 


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        from collections import defaultdict
        if len(s) != len(t): return False
        i = 0
        j = defaultdict(int)
        print((len(s)))
        while i < len(s):
            mr = (ord(t[i]) - ord(s[i]))%26
            if mr == 0:
                pass
            else:
                if mr + j.get(mr,0) * 26 > k:
                    return False
                j[mr] += 1
            i += 1
        return True
        
        


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s)!=len(t):
            return False
        
        hash_map = {}
        for i in range(len(s)):
            if s[i]!=t[i]:
                diff = -1*(ord(s[i])-ord(t[i]))
                if diff<0:
                    diff = 26+diff
                if diff in hash_map:
                    hash_map[diff]+=1
                    diff += (hash_map[diff]-1)*26
                else:
                    hash_map[diff] = 1
                if diff>k:
                   return False
        return True
                    


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        available, maxi = [0 if k < i else 1 + (k - i) // 26 for i in range(26)], 0
        for a, b in zip(s, t):
            if a == b:
                continue
            require = (26 + (ord(b) - ord('a')) - (ord(a) - ord('a'))) % 26
            if not available[require]:
                return False
            available[require] -= 1
            
            maxi = max(maxi, require)
            
        return maxi <= k

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        counts = [0] * 26
        for si, ti in zip(s, t):
            difference = ord(ti) - ord(si)
            if difference < 0:
                difference += 26
            counts[difference] += 1
        
        for i, count in enumerate(counts[1:], 1):
            maxConvert = i + 26 * (counts[i] - 1)
            if maxConvert > k:
                return False
        
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        n = len(s)
        occ = {}
        for i in range(n):
            l = (ord(t[i]) - ord(s[i]))%26
            if not l:
                continue
            try:
                if occ[l]:
                    occ[l] += 1
                    l = (occ[l]-1)*26 + l
                    if l > k:
                        return False
            except: 
                if l > k:
                    return False
                occ[l] = 1
        
        return True

from collections import defaultdict
class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = defaultdict(int)
        res = 0
        for i in range(len(s)):
            j = (ord(t[i]) - ord(s[i]) + 26) % 26
            if j:
                res = max(res, 26 * cnt[j] + j)
                cnt[j] += 1
        return res <= k

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        shift_needed = collections.defaultdict(int)
        for sc, tc in zip(s, t):
            if sc > tc:
                shift_needed[ord('z')-ord(sc)+ord(tc)-ord('a')+1] += 1
            elif sc < tc:
                shift_needed[ord(tc)-ord(sc)] += 1
                
        min_move_needed = 0
        for shift, v in list(shift_needed.items()):
            min_move_needed = max(min_move_needed, 26*(v-1)+shift)
        #print(shift_needed, min_move_needed)
        return min_move_needed <= k


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        d = {}
        if(len(s)!= len(t)):
            return False
        for i in range(len(s)):
            if(s[i]!= t[i]):
                if(ord(s[i])<ord(t[i])):
                    val = ord(t[i])-ord(s[i])
                else:
                    val = (ord('z')-ord(s[i]))+(ord(t[i])-ord('a'))+1
                if(val in d):
                    d[val]+=1
                elif(val not in d):
                    d[val] = 1
        for x in d:
            if(((d[x]-1)*26+x)>k):
                return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        maps = {}
        for i in range(len(s)):
            if s[i] != t[i]:
                diff = (ord(t[i]) - ord(s[i]) ) % 26
                if diff not in list(maps.keys()):
                    maps[diff] = 1
                else:
                    maps[diff] += 1
                if ((maps[diff] - 1) * 26 + diff) > k:
                    return False
        return True
                
        


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

        dists = [(26 + ord(b) - ord(a)) % 26 for a, b in zip(s, t)]
        counter = Counter(dists)
        print((dists, counter))
        for i in range(1, 26):
            if counter[i] > (k - i) // 26 + 1:
                return False
        
        return True
            


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if(len(s) != len(t)):
            return False
        idx_set = {0}
        idx_list = []
        idx_dict = {}
        for i in range(1, 26):
            idx_dict[i] = 0
        
        for idx, sc in enumerate(s):
            tc = t[idx]
            
            if(sc == tc):
                # idx_list.append(0)
                continue
            
            sasc = ord(sc)
            tasc = ord(tc)
            
            if(sasc < tasc):
                movei = tasc - sasc
            else:
                movei = 26 - sasc + tasc
            # while(movei in idx_set):
            #         movei = movei + 26
            origini = movei
            movei = movei + 26 * idx_dict[movei]
            idx_dict[origini] += 1
            if(movei > k):
                return False
            # idx_list.append(movei)
            # idx_set.add(movei)
        #print(idx_list)
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        if len(s) != len(t):
            return False
        
        def aIntoB(a,b)->int:
            return (ord(b)-ord(a)) % 26
        
        moves = [k//26]*26
        for i in range((k % 26) + 1):
            moves[i] += 1
            
        for a, b in zip(s, t):
            if a == b:
                continue
                
            moves[aIntoB(a,b)] -= 1
            if moves[aIntoB(a,b)] < 0:
                return False
            
        return True
        
#         3 ->
#         1 1 1 0 0 0 ...
        
#         29 ->
#         2 2 2 1 1 1 ...
        
#         27 ->
#         2 1 1 1 1 1 ...


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t): 
            return False
        diff = [(ord(c2)-ord(c1)) % 26 for c1, c2 in zip(s, t)]
        ctr = sorted((v, k) for k, v in list(collections.Counter(diff).items()) if k)
        return not ctr or (ctr[-1][0]-1) * 26 + ctr[-1][1] <= k
        


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        
        count = {}
        for x,y in zip(s,t):
            change = 0
            if ord(y) - ord(x) > 0:
                change = ord(y) - ord(x)
            elif ord(y) - ord(x) < 0:
                change = (ord(y) - ord(x)) + 26
                
            if change == 0:
                continue
                
            if change not in count:
                count[change] = 1
            else:
                count[change] += 1
            
            
            if (count[change] - 1) * 26 + change > k:
                return False
        
        
                    
        return True
        


class Solution:
    def canConvertString(self, S: str, T: str, k: int) -> bool:
        if len(S) != len(T):
            return False
        dic = {}
        for s, t in zip(S, T):
            shift = (ord(t) - ord(s))%26
            if not shift:
                continue
            if shift not in dic:dic[shift] = 0
            dic[shift] += 1
            if shift + 26*(dic[shift] - 1) > k:
                return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        # convert s to t in k moves or less
        # so the ith move is 1 <= i <= k
        # pick a character at j (1-indexed) in the string and shift it i times
        # or you can do nothing in the move.
        # 'shifting' the character means to replace it to the next letter in the alphabet
        alpha = 'abcdefghijklmnopqrstuvwxyz'
        # any index j can be picked at most ONCE
        # for each x  [1..k] you have an opportunity to shift a character in s, i times.
        # the answer is false if there is a character that needs more shifts than we are able to supply
        # can create a list of deltas, sorted descending, and see if we have enough space to work with
        deltas = []
        if len(s) != len(t): return False
        for i,c in enumerate(s):
            t_index = ord(t[i]) - ord('a')
            s_index = ord(s[i]) - ord('a')
            deltas.append((t_index - s_index)%26)
        m = collections.defaultdict(int)
        while k%26 != 0:
            m[k%26] += 1
            k -= 1
        for i in range(1,26):
            m[i] += k//26
        #print(sorted(deltas, reverse=True))
        for d in sorted(deltas, reverse=True):
            if not d:
                continue
            if not m[d]:
                return False
            m[d] -= 1
            # take the highest available k that will satisfy that delta
            # ie, take the highest number x such that x%26 == d %26
            # or you can have a count of all the numbers that land in each class
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        valid = {}
        moves = []
        for a,b in zip(s,t):
            if a != b:
                diff = ord(b) - ord(a)
                if diff < 0:
                    diff += 26
                if diff in valid:
                    valid[diff].append(valid[diff][-1]+26)
                else:
                    valid.setdefault(diff,[diff])
                moves.append(diff)
        for d in moves:
            num = valid[d]
            if num[-1] > k:
                return False
            else:
                num.pop()
        return True


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        n = len(s)
        m = len(t)
        if(n!=m):
            return False
        else:
            diff = {}
            d = {}
            for i in range(n):
                if(s[i]!=t[i]):
                    if(t[i]>s[i]):
                        value = ord(t[i])-ord(s[i])
                    else:
                        value = (26-ord(s[i]))+ord(t[i])
                    if value not in diff:
                        start = value
                    else:
                        start = diff[value]+26 
                    flag = 0
                    while(start<=k):
                        if start not in d:
                            d[start] = 1
                            diff[value] = start
                            flag = 1
                            break
                        start+=26
                    if(flag==0):
                        return False 
            return True

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

        n=len(s)

        for i in range(n):
            x=ord(t[i])-ord(s[i])
            if x==0:
                continue
            if x>0:
                if x in hash:
                    hash[x]+=[x+26*(len(hash[x]))]
                else:
                    hash[x]=[x]
            elif x<0:
                if 26+x in hash:
                    hash[26+x]+=[26+x+26*(len(hash[26+x]))]
                else:
                    hash[26+x]=[26+x]
        for a in hash:
            if a>k:
                return False
            for i in hash[a]:
                if i>k:
                    return False
        return True                

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        
        if len(s) != len(t):
            return False
        
        
        C = Counter()
        seen = set()
        for i in range(len(s)):
            if s[i] != t[i]:
                dist = (ord(t[i]) + 26 - ord(s[i])) % 26
                if dist not in C.keys():
                    C[dist] = 0
                else:
                    C[dist] += 1
                    dist += 26 * (C[dist]) 
                if dist > k:
                    return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        n = len(s)
        g = [0 for i in range(26)]
        for i in range(n):
            g[(ord(t[i]) - ord(s[i])) % 26] += 1
        for i in range(1, 26):
            index = i + (g[i]-1) * 26
            if index > k:
                return False
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        def getScore(sc, tc):
            if ord(sc) <= ord(tc):
                return ord(tc) - ord(sc)
            return ord('z') - ord(sc) + 1 + ord(tc) - ord('a') 
        
        if len(s) != len(t):
            return False
        
        score_ref = dict()
        for idx in range(len(s)):
            score = getScore(s[idx], t[idx])
            if score == 0:
                continue
            score_ref[score] = score if score_ref.get(score, 0) == 0 else score_ref[score] + 26
        
        return all([score_ref[score] <= k for score in score_ref])

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        n,m = len(s), len(t)
        if n != m:
            return False
        ls = [ord(j)-ord(i) for i, j in zip(s,t)]
        for i in range(n):
            if ls[i] < 0:
                ls[i] = 26 + ls[i]
        d = {}
        ans = 0
        # print(ls)
        for i in ls:
            if i == 0:
                continue
            if i not in d:
                ans = max(ans,i)
                d[i] = 1
            else:
                ans = max(26*d[i]+i, ans)
                d[i] += 1
            if ans > k:
                # print(ans, k, d)
                return False
        return True
        


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:

        if len(s) != len(t): return False
        mp = {}
        for i in range(len(s)): 
            v =  ord(t[i]) - ord(s[i])
            if v == 0: 
                continue
            if v < 0: 
                v += 26 # shift backward
            if v > k: 
                return False
            if v in mp: 
                # the highest number
                high_v = mp[v] + 26
                if high_v > k: 
                    return False
                mp[v] = high_v
            else:
                mp[v] = v
            
        return True

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        cnt = [0] * 26
        for cs, ct in zip(s, t):
            diff = (ord(ct) - ord(cs)) % 26
            if diff > 0 and cnt[diff] * 26 + diff > k:
                return False
            cnt[diff] += 1
        return True
                    


class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        b=0
        flag=0
        lis=[]
        if(len(s)==len(t)):
            for i in range(len(s)):
                if(s[i]!=t[i]):
                    if(s[i]<t[i]):
                        lis.append(ord(t[i])-ord(s[i]))
                    else:
                        lis.append(26-(ord(s[i])-ord(t[i])))
            lis.sort()
            i=0
            c=0
            while(i<len(lis)-1):
                if(lis[i]==lis[i+1]):
                    c=c+1
                else:
                    if(lis[i]+(c*26)>k):
                        flag=1
                        break
                    else:
                        c=0
                i=i+1
            if(len(lis)>1):
                if(lis[-1]!=lis[-2]):
                    if(lis[-1]>k):
                        flag=1
            if(len(lis)>0):
                    if(lis[i-1]+(c*26)>k):
                        flag=1
            if(flag==0):
                b=1
        return(b)

class Solution:
    def canConvertString(self, s: str, t: str, k: int) -> bool:
        if len(s) != len(t):
            return False
        count = {}
        total = [0]
        # print(count)
        for i in range(len(s)):
            if ord(s[i]) > ord(t[i]):
                # print('case {} {}'.format(s[i], t[i]))
                x = 122 - ord(s[i]) + ord(t[i]) - 96
            else:
                x = ord(t[i]) - ord(s[i])
            # print(\"({} {})\".format(x,i))
            if x != 0:
                if x not in count:
                    count[x] = 0
                if count[x] * 26 + x:
                    max = count[x] * 26 + x
                    if max > k:
                        return False
                count[x] += 1
        # print(max(total))
        return True