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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

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
		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
		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
			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]
		for i in range(len(s)):
			if ord(s[i]) > ord(t[i]):
				x = 122 - ord(s[i]) + ord(t[i]) - 96
			else:
				x = ord(t[i]) - ord(s[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
		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]
		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])


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)
			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
			if shift_amount in shift_used:
				if 26 * shift_used[shift_amount] + shift_amount > k:
					return False
				else:
					shift_used[shift_amount] += 1
			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
			elif 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


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)):
			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
		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
		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:

	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:
		n1 = len(s)
		n2 = len(t)
		if n1 != n2:
			return False
		n = n1
		diffArray = [(ord(t[i]) - ord(s[i])) % 26 for i in range(n)]
		cda = collections.Counter(diffArray)
		del cda[0]
		minK = 0
		if len(cda) > 0:
			key = max([(i[1], i[0]) for i in list(cda.items())])
			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
		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


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
		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:
		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
		idx_dict = [0] * 26
		for (idx, sc) in enumerate(s):
			tc = t[idx]
			if sc == tc:
				continue
			sasc = ord(sc)
			tasc = ord(tc)
			if sasc < tasc:
				movei = tasc - sasc
			else:
				movei = 26 - sasc + tasc
			origini = movei
			movei = movei + 26 * idx_dict[movei]
			idx_dict[origini] += 1
			if movei > 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)
		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 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
		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:
		n1 = len(s)
		n2 = len(t)
		if n1 != n2:
			return False
		n = n1
		diffArray = [(ord(t[i]) - ord(s[i])) % 26 for i in range(n)]
		cda = collections.Counter(diffArray)
		print(cda)
		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
				elif 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:
		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
		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):
			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:
			if (cnt[r] - 1) * 26 + r > 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 = {}
		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
			elif 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
		visited = {}
		for (ss, tt) in zip(s, t):
			if ss != tt:
				d = (ord(tt) - ord(ss)) % 26
				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
		(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)
		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) 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

		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


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:
		alpha = 'abcdefghijklmnopqrstuvwxyz'
		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
		for d in sorted(deltas, reverse=True):
			if not d:
				continue
			if not m[d]:
				return False
			m[d] -= 1
		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
		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:
				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
			if v > k:
				return False
			if v in mp:
				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:
		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
				elif 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