Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B.
Given two anagrams A and B, return the smallest K for which A and B are K-similar.
Example 1:
Input: A = "ab", B = "ba"
Output: 1


Example 2:
Input: A = "abc", B = "bca"
Output: 2


Example 3:
Input: A = "abac", B = "baca"
Output: 2


Example 4:
Input: A = "aabc", B = "abca"
Output: 2



Note:

1 <= A.length == B.length <= 20
A and B contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Graph traversal

Starter code: class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        

Solutions:
class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		a = ''
		b = ''
		for i in range(len(A)):
			if A[i] != B[i]:
				a += A[i]
				b += B[i]
		return self.dfs(a, b)

	def dfs(self, a, b):
		if not a:
			return 0
		one = []
		two = []
		for i in range(len(a)):
			if a[0] == b[i]:
				one.append(i)
				if b[0] == a[i]:
					two.append(i)
		if two:
			i = two[0]
			c = a[1:i] + a[i + 1:]
			d = b[1:i] + b[i + 1:]
			return self.dfs(c, d) + 1
		else:
			res = float('inf')
			for i in one:
				c = a[i] + a[1:i] + a[i + 1:]
				d = b[:i] + b[i + 1:]
				res = min(res, self.dfs(c, d) + 1)
			return res


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0

		def neighbors(s, i=0):
			while s[i] == B[i]:
				i += 1
			for j in range(i + 1, len(A)):
				if s[j] == B[i] and B[j] == s[i]:
					yield (s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])
					return
			for j in range(i + 1, len(A)):
				if s[j] == B[i] and s[j] != B[j]:
					yield (s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])
		dp = collections.deque([(A, 0)])
		met = set()
		while dp:
			(A_, step) = dp.popleft()
			for n in neighbors(A_):
				if n == B:
					return step + 1
				if n not in met:
					dp.append((n, step + 1))
					met.add(n)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		(lsta, lstb) = ('', '')
		for i in range(len(A)):
			if A[i] != B[i]:
				lsta += A[i]
				lstb += B[i]
		q = [(0, lsta, lstb)]
		while q:
			(time, la, lb) = q.pop(0)
			if not lb:
				return time
			goal = lb[0]
			(work, ls) = (None, [])
			for i in range(1, len(la)):
				if la[i] == goal and la[0] == lb[i]:
					work = True
					break
			if work:
				q.append((time + 1, la[1:i] + la[i + 1:], lb[1:i] + lb[i + 1:]))
			else:
				for i in range(1, len(la)):
					if la[i] == goal:
						q.append((time + 1, la[1:i] + la[0] + la[i + 1:], lb[1:]))


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		A = list(A)
		memo = {}

		def solution(i):
			t = tuple(A)
			if (i, t) in memo:
				return memo[i, t]
			if i == len(A):
				return 0
			if A[i] == B[i]:
				return solution(i + 1)
			mymin = float('inf')
			for j in range(i + 1, len(A)):
				if A[j] != B[i]:
					continue
				(A[i], A[j]) = (A[j], A[i])
				mymin = min(mymin, solution(i + 1))
				(A[j], A[i]) = (A[i], A[j])
			memo[i, t] = 1 + mymin
			return 1 + mymin
		return solution(0)


from collections import deque

class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def swapPos(string):
			i = 0
			while string[i] == B[i]:
				i += 1
			for j in range(i + 1, length):
				if string[j] == B[i]:
					yield (string[:i] + string[j] + string[i + 1:j] + string[i] + string[j + 1:])
		dq = deque([(A, 0)])
		visited = set(A)
		length = len(A)
		while dq:
			(string, dist) = dq.popleft()
			if string == B:
				return dist
			for s2 in swapPos(string):
				if s2 not in visited:
					dq.append((s2, dist + 1))
					visited.add(s2)


class Solution:

	@lru_cache(maxsize=None)
	def kSimilarity(self, A: str, B: str) -> int:
		if not A and (not B):
			return 0
		if A[0] == B[0]:
			return self.kSimilarity(A[1:], B[1:])
		ans = float('inf')
		for (i, c) in enumerate(B):
			if c == A[0]:
				ans = min(ans, 1 + self.kSimilarity(A[1:], B[1:i] + B[0] + B[i + 1:]))
		return ans


from functools import lru_cache

class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		n = len(A)

		@lru_cache(None)
		def dfs(s):
			if s == B:
				return 0
			idx = 0
			while s[idx] == B[idx]:
				idx += 1
			res = float('inf')
			for nxt in range(idx + 1, n):
				if s[nxt] != B[idx]:
					continue
				res = min(res, dfs(s[:idx] + s[nxt] + s[idx + 1:nxt] + s[idx] + s[nxt + 1:]) + 1)
			return res
		return dfs(A)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		q = collections.deque()
		visited = set()
		q.append(A)
		visited.add(A)
		step = -1
		while q:
			step += 1
			lens = len(q)
			for _ in range(lens):
				curr = q.popleft()
				if curr == B:
					return step
				for next in self._swap(curr, B):
					if next in visited:
						continue
					q.append(next)
					visited.add(next)

	def _swap(self, s, B):
		i = 0
		while s[i] == B[i]:
			i += 1
		for j in range(i + 1, len(s)):
			if s[j] == B[i]:
				yield (s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])


class Solution:

	def kSimilarity(self, A, B):

		def nei(x):
			i = 0
			while x[i] == B[i]:
				i += 1
			for j in range(i + 1, len(A)):
				if x[j] == B[j]:
					continue
				if x[j] == B[i] and x[i] == B[j]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
					break
				if x[j] == B[i]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
		stack = [(A, 0)]
		visit = {A}
		for (cur, d) in stack:
			if cur == B:
				return d
			for neighbor in nei(cur):
				if neighbor not in visit:
					visit.add(neighbor)
					stack.append((neighbor, d + 1))


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def find(s):
			i = 0
			res = []
			while s[i] == B[i]:
				i += 1
			for j in range(i + 1, len(B)):
				if s[j] == B[i]:
					res.append(s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])
			return res
		q = collections.deque([[0, A]])
		seen = set([A])
		while q:
			size = len(q)
			for _ in range(size):
				(step, s) = q.popleft()
				if s == B:
					return step
				for new in find(s):
					if new not in seen:
						seen.add(new)
						q.append([step + 1, new])
		return


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def nei(x):
			i = 0
			while x[i] == B[i]:
				i += 1
			for j in range(i + 1, len(x)):
				if x[i] == B[j] and x[j] != B[j]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
		seen = {A}
		queue = [(A, 0)]
		for (node, change) in queue:
			if node == B:
				return change
			for y in nei(node):
				if y not in seen:
					seen.add(node)
					queue.append((y, change + 1))


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def nei(x):
			i = 0
			while x[i] == B[i]:
				i += 1
			for j in range(i + 1, len(x)):
				if x[j] == B[i]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
		(q, seen) = ([(A, 0)], {A})
		for (x, d) in q:
			if x == B:
				return d
			for y in nei(x):
				if y not in seen:
					(seen.add(y), q.append((y, d + 1)))


from collections import deque

class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def successor(s):
			i = 0
			while s[i] == B[i]:
				i += 1
			for j in range(i, len(s)):
				if s[j] == B[i]:
					yield (s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])
		q = deque([(A, 0)])
		seen = set()
		while q:
			(curr, dist) = q.popleft()
			if curr == B:
				return dist
			if curr not in seen:
				seen.add(curr)
				q.extend([(suc, dist + 1) for suc in successor(curr)])


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		N = len(A)

		def dfs(A, B, pos):
			if A == B:
				return 0
			while A[pos] == B[pos]:
				pos += 1
			minCnt = float('inf')
			for i in range(pos + 1, N):
				if B[i] == A[pos] and B[i] != A[i]:
					(B[i], B[pos]) = (B[pos], B[i])
					tmp = dfs(A, B, pos + 1) + 1
					minCnt = min(tmp, minCnt)
					(B[i], B[pos]) = (B[pos], B[i])
			return minCnt
		return dfs(list(A), list(B), 0)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		A = list(A)
		B = list(B)
		n = len(A)

		def rec(i):
			if i == n:
				return 0
			if A[i] == B[i]:
				return rec(i + 1)
			else:
				min_ = sys.maxsize
				for j in range(i + 1, n):
					if B[j] == A[i] and B[j] != A[j]:
						(B[i], B[j]) = (B[j], B[i])
						min_ = min(min_, rec(i + 1) + 1)
						(B[i], B[j]) = (B[j], B[i])
				return min_
		return rec(0)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		return do_kSimilarity(list(A), list(B), {})

def do_kSimilarity(A, B, memo):
	if (tuple(A), tuple(B)) in memo:
		return memo[tuple(A), tuple(B)]
	if A == B:
		return 0
	if A[0] == B[0]:
		return do_kSimilarity(A[1:], B[1:], memo)
	else:
		swaps = []
		for (i, char) in enumerate(A):
			if char == B[0]:
				swaps.append(i)
		k = float('inf')
		for swap in swaps:
			(A[0], A[swap]) = (A[swap], A[0])
			k = min(k, 1 + do_kSimilarity(A[1:], B[1:], memo))
			(A[0], A[swap]) = (A[swap], A[0])
		memo[tuple(A), tuple(B)] = k
		return k


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def neighbor(s):
			i = 0
			while i < len(B) and s[i] == B[i]:
				i += 1
			for j in range(i + 1, len(B)):
				if s[j] == B[i]:
					yield (s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])
		queue = deque([(A, 0)])
		visited = {A}
		while queue:
			(s, d) = queue.popleft()
			if s == B:
				return d
			for n in neighbor(s):
				if n not in visited:
					visited.add(n)
					queue.append([n, d + 1])


class Solution:

	def bfs(self, A: str, B: str):
		if A == B:
			return 0
		n = len(A)
		q = []
		visited = set()
		q.append((B, 0, 0))
		while q:
			(processed, idx, swaps) = q.pop(0)
			visited.add(processed)
			while processed[idx] == A[idx]:
				idx += 1
			for i in range(idx + 1, n):
				if A[idx] == processed[i]:
					new_processed = processed[:idx] + processed[i] + processed[idx + 1:i] + processed[idx] + processed[i + 1:]
					if A == new_processed:
						return swaps + 1
					if new_processed not in visited:
						q.append((new_processed, idx + 1, swaps + 1))
		return 0

	def kSimilarity(self, A: str, B: str) -> int:
		return self.bfs(A, B)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def neighbors(A):
			i = 0
			while A[i] == B[i]:
				i += 1
			for j in range(i + 1, len(B)):
				if A[i] != A[j] and A[j] == B[i]:
					yield (A[:i] + A[j] + A[i + 1:j] + A[i] + A[j + 1:])
		queue = [(A, 0)]
		seen = set([A])
		for (s, val) in queue:
			if s == B:
				return val
			for nxt_s in neighbors(s):
				if nxt_s not in seen:
					queue.append((nxt_s, val + 1))
					seen.add(nxt_s)
		return -1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		self.min = float('inf')
		A = list(A)
		B = list(B)

		def swap(a, b):
			(A[a], A[b]) = (A[b], A[a])

		@lru_cache(None)
		def helper(left, right, AB):
			ok = True
			swaps = 0
			while A != B:
				ok = False
				a = A[left]
				b = B[right]
				if a != b:
					minn = float('inf')
					poss = []
					for (i, c) in enumerate(A):
						if b == c and i >= left:
							poss.append(i)
					for p in poss:
						swap(left, p)
						otherswaps = helper(left + 1, right + 1, tuple(A + B))
						swap(left, p)
						minn = min(otherswaps, minn)
					return swaps + 1 + minn
				left = (left + 1) % len(A)
				right = (right + 1) % len(B)
			return swaps
		f = helper(0, 0, tuple(A + B))
		print(A)
		print(B)
		return f


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		dq = deque([(A, 0)])
		cnt = 0
		N = len(A)
		while dq:
			length = len(dq)
			for _ in range(length):
				(curr, idx) = dq.popleft()
				lst = list(curr)
				for i in range(idx, N):
					if lst[i] != B[i]:
						for j in range(i + 1, N):
							if lst[j] != B[j] and lst[j] == B[i]:
								(lst[i], lst[j]) = (lst[j], lst[i])
								temp = ''.join(lst)
								if temp == B:
									return cnt + 1
								dq.append((temp, i + 1))
								(lst[i], lst[j]) = (lst[j], lst[i])
						break
			cnt += 1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def dist(a, b):
			return sum((1 if c != d else 0 for (c, d) in zip(a, b)))

		def swap(s, i, j):
			if i > j:
				(i, j) = (j, i)
			return s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]

		def DFS(string, k):
			if string == A:
				return True
			if k == 0:
				return False
			for (i, c) in enumerate(string):
				if A[i] == c:
					continue
				for j in range(i, len(A)):
					if string[j] == A[i] and A[j] != A[i]:
						if DFS(swap(string, i, j), k - 1):
							return True
				return False
		for k in range(len(A)):
			if DFS(B, k):
				return k


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		N = len(A)
		if not N:
			return 0
		cnt = 0
		q = deque()
		q.append((cnt, A, 0))
		while q:
			(cnt, v, i) = q.popleft()
			if v == B:
				return cnt
			for j in range(i + 1, N):
				while v[i] == B[i]:
					i += 1
				if v[j] == B[i] and v[j] != B[j]:
					candidate = v[:i] + v[j] + v[i + 1:j] + v[i] + v[j + 1:]
					q.append((cnt + 1, candidate, i + 1))


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		self.counter = float('inf')
		A = list(A)
		B = list(B)

		def swap(first, cur):
			if first == len(A) - 1 or A[first:] == B[first:]:
				self.counter = min(self.counter, cur)
				return
			for i in range(first, len(A)):
				if A[i] != B[i]:
					for k in range(i + 1, len(A)):
						if A[i] == B[k] and cur + 1 < self.counter:
							(B[i], B[k]) = (B[k], B[i])
							swap(i + 1, cur + 1)
							(B[i], B[k]) = (B[k], B[i])
					break
			return
		swap(0, 0)
		return self.counter


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def dfs(A, B):
			if not A and (not B):
				return 0
			if str(A) == str(B):
				return 0
			k = str(A)
			if k in dp:
				return dp[k]
			dp[k] = len(A) - 1
			if A[0] == B[0]:
				dp[k] = dfs(A[1:], B[1:])
				return dp[k]
			for j in range(1, len(A)):
				if A[j] == B[0]:
					(A[0], A[j]) = (A[j], A[0])
					dp[k] = min(dp[k], 1 + dfs(A[1:], B[1:]))
					(A[j], A[0]) = (A[0], A[j])
			return dp[k]
		dp = dict()
		(A, B) = (list(A), list(B))
		dp[str(A)] = dfs(A, B)
		return dp[str(A)]


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def dist(a, b):
			return sum((1 if c != d else 0 for (c, d) in zip(a, b)))

		def swap(s, i, j):
			if i > j:
				(i, j) = (j, i)
			return s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]

		def DFS(string, k, seen):
			if string in seen:
				return (False, 0)
			seen.add(string)
			if string == A:
				return (True, 1)
			distance = dist(string, A)
			best = distance / 2 if distance % 2 == 0 else distance // 2 + 1
			if k < best:
				return (False, 1)
			neighbors = []
			for (i, c) in enumerate(string):
				if A[i] == c:
					continue
				for j in range(i + 1, len(A)):
					if string[j] == A[i] and A[j] != A[i]:
						double_play = string[i] == A[j]
						change = -2 if double_play else -1
						if k == best and distance % 2 == 1 and (distance > 3) and (not double_play):
							continue
						neighbor = swap(string, i, j)
						neighbors.append((change, neighbor))
			neighbors.sort()
			total_count = 1
			for (score, neighbor) in neighbors:
				(found, count) = DFS(neighbor, k - 1, seen)
				total_count += count
				if found:
					return (True, total_count)
			return (False, total_count)
		for k in range(len(A), -1, -1):
			(found, count) = DFS(B, k, set())
			if not found:
				return k + 1
		return 0


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def neighbor(x):
			i = 0
			while x[i] == B[i]:
				i += 1
			for j in range(i + 1, len(x)):
				if x[j] == B[i] and x[j] != B[j]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
		(queue, seen) = ([(A, 0)], {A})
		for (word, distance) in queue:
			if word == B:
				return distance
			for neigh in neighbor(word):
				if neighbor not in seen:
					seen.add(neigh)
					queue.append((neigh, distance + 1))


from collections import deque

class Solution:

	def kSimilarity(self, A, B):

		def find_neighbors(arr, i):
			e = A[i]
			nei = []
			for x in range(i + 1, len(arr)):
				if arr[x] == e:
					nei.append(x)
			return nei
		q = deque()
		for i in range(len(A)):
			if A[i] == B[i]:
				continue
			else:
				q.append([list(B), i])
				break
		l = 0
		while q:
			for x in range(len(q)):
				e = q.popleft()
				y = e[1]
				while y < len(e[0]):
					if e[0][y] == A[y]:
						y += 1
					else:
						break
				if y == len(e[0]):
					return l
				else:
					nei = find_neighbors(e[0], y)
					for n in nei:
						new_e = e[0][:]
						new_e[n] = e[0][y]
						q.append([new_e, y + 1])
			l += 1
		return l


class Solution:

	def kSimilarity(self, A, B):
		out = 0
		q = deque()
		for i in range(len(A)):
			if A[i] == B[i]:
				continue
			else:
				q.append([list(B), i])
				break

		def find_neighbors(arr, i):
			e = A[i]
			nei = []
			for x in range(i + 1, len(arr)):
				if arr[x] == e:
					nei.append(x)
			return nei
		while q:
			for _ in range(len(q)):
				(cur, idx) = q.popleft()
				while idx < len(cur):
					if cur[idx] == A[idx]:
						idx += 1
					else:
						break
				if idx == len(cur):
					return out
				else:
					nei = find_neighbors(cur, idx)
					for n in nei:
						new = cur[:]
						new[n] = cur[idx]
						q.append([new, idx + 1])
			out += 1
		return out


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def check(a, i):
			if a == B:
				return 0
			if a[i] != B[i]:
				j = i
				minCount = None
				while j < len(a):
					if a[j] == B[i]:
						if a[i] == B[j]:
							return 1 + check(a[:i] + a[j] + a[i + 1:j] + a[i] + a[j + 1:], i + 1)
						count = check(a[:i] + a[j] + a[i + 1:j] + a[i] + a[j + 1:], i + 1)
						if minCount == None or minCount > count:
							minCount = count
					j += 1
				return 1 + minCount
			else:
				return 0 + check(a, i + 1)
		return check(A, 0)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		(A, B) = (list(A), list(B))
		res = float('inf')
		q = [(0, 0, B)]
		while q:
			(i, k, B) = heapq.heappop(q)
			i = -i
			if k >= res:
				continue
			while i < len(B) and B[i] == A[i]:
				i += 1
			if i == len(B):
				res = min(res, k)
				continue
			target = A[i]
			j = i + 1
			while j < len(B):
				if B[j] == target:
					heapq.heappush(q, (-(i + 1), k + 1, B[:j] + [B[i]] + B[j + 1:]))
				j += 1
		return res


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		(visited, n) = (set(), len(A))
		q = collections.deque([(A, 0)])
		while q:
			(C, swaps) = q.popleft()
			if C == B:
				return swaps
			visited.add(C)
			i = 0
			while C[i] == B[i]:
				i += 1
			for j in range(i + 1, n):
				if C[j] == B[i]:
					nxt = C[:i] + C[j] + C[i + 1:j] + C[i] + C[j + 1:]
					if nxt not in visited:
						q.append((nxt, swaps + 1))
		return -1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def dist(a, b):
			return sum((1 if c != d else 0 for (c, d) in zip(a, b)))

		def find_wrong_letters(working):
			wants = defaultdict(set)
			wrongs = defaultdict(set)
			for (i, c) in enumerate(working):
				target = A[i]
				if c != target:
					wants[target].add(i)
					wrongs[c].add(i)
			return (wants, wrongs)

		def estimate_remaining(string):
			count = dist(string, A)
			return count / 2 if count % 2 == 0 else count // 2 + 1

		def swap(s, i, j):
			if i > j:
				(i, j) = (j, i)
			return s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]

		def extend(working):
			(wrongs, needs) = find_wrong_letters(working)
			for (letter, wrong_set) in list(wrongs.items()):
				return (swap(working, i, j) for i in wrong_set for j in needs[letter])
		if A == B:
			return 0
		q = [(0, 0, B)]
		seen = dict()
		best = len(A)
		while q:
			(estimate, k, working) = heapq.heappop(q)
			if estimate >= best or k >= best:
				return best
			if working == A:
				best = min(best, k)
				continue
			for extension in extend(working):
				if extension not in seen or seen[extension] > k + 1:
					seen[extension] = k + 1
					new_estimate = estimate_remaining(extension) + k + 1
					heapq.heappush(q, (new_estimate, k + 1, extension))
		return best


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		m = len(A)

		def getNeighbors(word):
			i = 0
			while word[i] == B[i]:
				i += 1
			for j in range(i + 1, m):
				if word[j] == B[i]:
					yield (word[:i] + word[j] + word[i + 1:j] + word[i] + word[j + 1:])
		visited = set([A])
		queue = collections.deque([A])
		k = 1
		while queue:
			for _ in range(len(queue)):
				word = queue.popleft()
				for nbor in getNeighbors(word):
					if nbor not in visited:
						if nbor == B:
							return k
						queue.append(nbor)
			k += 1
		raise Exception('invalid')


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		n = len(B)
		q = deque([B])
		visited = {B}
		cnt = 0
		while q:
			L = len(q)
			for _ in range(L):
				cur = q.popleft()
				if cur == A:
					return cnt
				pos = 0
				while A[pos] == cur[pos]:
					pos += 1
				curlist = list(cur)
				for i in range(pos + 1, n):
					if curlist[i] == A[pos] and curlist[i] != A[i]:
						(curlist[i], curlist[pos]) = (curlist[pos], curlist[i])
						curstr = ''.join(curlist)
						if curstr not in visited:
							q.append(curstr)
						visited.add(curstr)
						(curlist[i], curlist[pos]) = (curlist[pos], curlist[i])
			cnt += 1
		return cnt


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def kSimilarity(self, A: str, B: str) -> int:
		if len(A) == 0:
			return 0
		if A[0] == B[0]:
			return self.kSimilarity(A[1:], B[1:])
		for i in range(1, len(B)):
			if A[0] == B[i] and B[0] == A[i]:
				return 1 + self.kSimilarity(A[1:i] + A[i + 1:], B[1:i] + B[i + 1:])
		ans = math.inf
		for i in range(1, len(B)):
			if A[0] == B[i]:
				ans = min(ans, 1 + self.kSimilarity(A[1:], B[1:i] + B[0] + B[i + 1:]))
		return ans


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0

		def swap(S, i, j):
			a = list(S)
			(a[i], a[j]) = (a[j], a[i])
			return ''.join(a)
		n = len(A)
		steps = 0
		q = deque()
		visited = set()
		q.append(A)
		visited.add(A)
		while q:
			steps += 1
			sz = len(q)
			for _ in range(sz):
				S = q.popleft()
				i = 0
				while S[i] == B[i]:
					i += 1
				for j in range(i + 1, n):
					if S[j] != B[i] or S[j] == B[j]:
						continue
					T = swap(S, i, j)
					if T == B:
						return steps
					if T not in visited:
						q.append(T)
						visited.add(T)
		return steps


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		seen = set(A)
		q = deque()
		q.append((A, 0))
		while q:
			(currentString, k) = q.popleft()
			for i in range(0, len(B) - 1):
				if currentString[i] == B[i]:
					continue
				for j in range(i + 1, len(B)):
					if currentString[j] == B[j]:
						continue
					if currentString[i] == currentString[j]:
						continue
					if currentString[j] != B[i]:
						continue
					newString = currentString[:i] + currentString[j] + currentString[i + 1:j] + currentString[i] + currentString[j + 1:]
					if newString == B:
						return k + 1
					if newString not in seen:
						q.append((newString, k + 1))
						seen.add(newString)
				break
		return -1


from collections import deque

class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		queue = deque([])
		queue.append(A)
		step = 0
		visited = set()
		while queue:
			length = len(queue)
			while length:
				length -= 1
				strings = queue.popleft()
				i = 0
				while strings[i] == B[i]:
					i += 1
				newstrings = list(strings)
				cha = strings[i]
				for j in range(i + 1, len(strings)):
					if strings[j] == B[i] and strings[j] != B[j]:
						(newstrings[i], newstrings[j]) = (newstrings[j], newstrings[i])
						newstrings = ''.join(newstrings)
						if newstrings == B:
							return step + 1
						elif newstrings not in visited:
							visited.add(newstrings)
							queue.append(newstrings)
						newstrings = list(strings)
			step += 1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def getNeighbors(s):
			for (i, c) in enumerate(s):
				if c != B[i]:
					break
			s = list(s)
			for j in range(i + 1, len(s)):
				if s[j] == B[i] and s[j] != B[j]:
					(s[i], s[j]) = (s[j], s[i])
					yield ''.join(s)
					(s[j], s[i]) = (s[i], s[j])
		queue = collections.deque([A])
		seen = {A: 0}
		while queue:
			s = queue.popleft()
			if s == B:
				return seen[s]
			for n in getNeighbors(s):
				if n not in seen:
					seen[n] = seen[s] + 1
					queue.append(n)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		l = len(A)

		def neighbor(s, pos, target):
			visited = set()
			t = list(s)
			for i in range(pos + 1, l):
				if t[i] == target and (t[i], B[i]) not in visited:
					visited.add((t[i], B[i]))
					(t[pos], t[i]) = (t[i], t[pos])
					yield ''.join(t)
					(t[pos], t[i]) = (t[i], t[pos])
		step = 0
		index = 0
		seen = set()
		q = collections.deque()
		q.append((A, 0))
		seen.add(A)
		while q:
			lq = len(q)
			for j in range(lq):
				(tmp, k) = q.popleft()
				if tmp == B:
					return step
				while k < l and tmp[k] == B[k]:
					k += 1
				for n in neighbor(tmp, k, B[k]):
					if n not in seen:
						seen.add(n)
						q.append((n, k))
			step += 1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		visited = set([A])
		q = collections.deque([A])
		(res, n) = (0, len(A))
		while q:
			res += 1
			qn = len(q)
			for _ in range(qn):
				s = q.popleft()
				i = 0
				while i < n and s[i] == B[i]:
					i += 1
				for j in range(i + 1, n):
					if s[j] == B[j] or s[j] != B[i]:
						continue
					tmp = self.swap(s, i, j)
					if tmp == B:
						return res
					if tmp not in visited:
						visited.add(tmp)
						q.append(tmp)
		return res

	def swap(self, s: str, i: int, j: int) -> str:
		l = list(s)
		(l[i], l[j]) = (l[j], l[i])
		return ''.join(l)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def dist(a, b):
			return sum((1 if c != d else 0 for (c, d) in zip(a, b)))

		def find_wrong_letters(working):
			wants = defaultdict(set)
			wrongs = defaultdict(set)
			for (i, c) in enumerate(working):
				target = A[i]
				if c != target:
					wants[target].add(i)
					wrongs[c].add(i)
			return (wants, wrongs)

		def swap(s, i, j):
			if i > j:
				(i, j) = (j, i)
			return s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]

		def extend(working):
			(wrongs, needs) = find_wrong_letters(working)
			for (letter, wrong_set) in list(wrongs.items()):
				return (swap(working, i, j) for i in wrong_set for j in needs[letter])
		q = deque()
		q.append((0, 0, B))
		seen = dict()
		best = len(A)
		while q:
			(estimate, k, working) = q.popleft()
			if estimate >= best or k >= best:
				return best
			if working == A:
				best = min(best, k)
				continue
			(improves_one, improves_two) = ([], [])
			for extension in extend(working):
				improvement = dist(A, working) - dist(A, extension)
				if improvement == 2:
					improves_two.append(extension)
				else:
					improves_one.append(extension)
			for extension in improves_two or improves_one:
				if extension not in seen or seen[extension] > k + 1:
					seen[extension] = k + 1
					q.append((0, k + 1, extension))
		return best


from collections import deque

class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		length = len(A)
		q = deque([A])
		visited = set([A])
		step = 0
		while q:
			size = len(q)
			for _ in range(size):
				cur = q.popleft()
				if cur == B:
					return step
				for i in range(length):
					if cur[i] != B[i]:
						break
				for j in range(i + 1, length):
					if cur[j] != B[j] and cur[j] == B[i]:
						new_str = cur[:i] + cur[j] + cur[i + 1:j] + cur[i] + cur[j + 1:]
						if new_str not in visited:
							q.append(new_str)
							visited.add(new_str)
			step += 1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def next(s):
			for i in range(len(s)):
				if s[i] != B[i]:
					for j in range(i + 1, len(s)):
						if B[i] == s[j] and B[j] == s[i]:
							yield (s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])
					for j in range(i + 1, len(s)):
						if B[i] == s[j] and B[j] != s[j]:
							yield (s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])
					return
		res = 0
		if A == B:
			return res
		q = [(A, 0)]
		seen = {A}
		for (s, i) in q:
			if s == B:
				return i
			for n in next(s):
				if n not in seen:
					q.append((n, i + 1))
					seen.add(n)
		return -1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def get_neis(s):
			res = []
			for i in range(N):
				if s[i] != B[i]:
					break
			temp = list(s)
			for j in range(i + 1, N):
				if s[j] == B[i] and s[j] != B[j]:
					(temp[i], temp[j]) = (temp[j], temp[i])
					res.append(''.join(temp))
					(temp[i], temp[j]) = (temp[j], temp[i])
			return res
		if A == B:
			return 0
		N = len(A)
		dq = deque([A])
		seen = set([A])
		cnt = 0
		while dq:
			length = len(dq)
			for _ in range(length):
				s = dq.popleft()
				for nei in get_neis(s):
					if nei == B:
						return cnt + 1
					if nei not in seen:
						seen.add(nei)
						dq.append(nei)
			cnt += 1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def swap(s):
			i = 0
			while s[i] == B[i]:
				i += 1
			for j in range(i + 1, len(s)):
				if s[j] == B[i] and B[j] != s[j]:
					yield (s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:])
		q = collections.deque([(A, 0)])
		seen = {A}
		while q:
			(s, d) = q.popleft()
			if s == B:
				return d
			for n in swap(s):
				if n not in seen:
					seen.add(n)
					q.append((n, d + 1))


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		(lsta, lstb) = ([], [])
		for i in range(len(A)):
			if A[i] != B[i]:
				lsta.append(A[i])
				lstb.append(B[i])
		(A, B) = (''.join(lsta), ''.join(lstb))
		q = deque([(0, A, B)])
		while q:
			(cost, curr, goal) = q.popleft()
			if not curr:
				return cost
			need = goal[0]
			work = None
			for i in range(len(curr)):
				if curr[i] == goal[0] and goal[i] == curr[0]:
					work = i
					break
			if work:
				q.append((cost + 1, curr[1:work] + curr[work + 1:], goal[1:work] + goal[work + 1:]))
			else:
				for i in range(1, len(curr)):
					if curr[i] == need:
						q.append((cost + 1, curr[1:i] + curr[0] + curr[i + 1:], goal[1:]))


from collections import deque

class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def nei(x):
			i = 0
			while x[i] == B[i]:
				i += 1
			for j in range(i + 1, len(x)):
				if x[j] == B[i] and x[j] != B[j]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
		if not A or not B:
			return 0
		(queue, visited) = ([(A, 0)], {A})
		for (x, d) in queue:
			if x == B:
				return d
			for y in nei(x):
				if y not in visited:
					visited.add(y)
					queue.append((y, d + 1))


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		dp = [B]
		visit = {B}
		k = 0
		while dp:
			k += 1
			l = len(dp)
			for i in range(l):
				s = dp.pop()
				for (j, c) in enumerate(A):
					if c != s[j]:
						for n in range(j + 1, len(A)):
							if s[n] == c:
								newS = s[0:j] + s[n] + s[j + 1:n] + s[j] + s[n + 1:]
								if newS not in visit:
									if newS == A:
										return k
									dp.insert(0, newS)
									visit.add(newS)
						break


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		memo = {}

		def helper(a, b):
			if a == b:
				return 0
			if (a, b) in memo:
				return memo[a, b]
			res = float('inf')
			if a[-1] == b[-1]:
				res = min(res, helper(a[:-1], b[:-1]))
			else:
				for i in range(len(a) - 1):
					if a[i] == b[-1] and a[i] != b[i]:
						a_new = a[:i] + a[-1] + a[i + 1:-1]
						res = min(res, 1 + helper(a_new, b[:-1]))
			memo[a, b] = res
			return res
		return helper(A, B)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		(q, visited) = ([(A, 0)], {A})
		for (x, dist) in q:
			if x == B:
				return dist
			for y in self.generate_neighbour_strings(x, B):
				if y not in visited:
					(visited.add(y), q.append((y, dist + 1)))

	def generate_neighbour_strings(self, x, B):
		i = 0
		while x[i] == B[i]:
			i += 1
		for j in range(i + 1, len(x)):
			if x[j] == B[i] and x[j] != B[j]:
				yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		queue = collections.deque([A])
		visited = set([A])
		step = 0
		while queue:
			for _ in range(len(queue)):
				curr = queue.popleft()
				for nxt in self.findNext(curr, B):
					if nxt == B:
						return step + 1
					if nxt in visited:
						continue
					queue.append(nxt)
					visited.add(nxt)
			step += 1
		return -1

	def findNext(self, curr, B):
		for i in range(len(curr)):
			if curr[i] != B[i]:
				break
		for j in range(i + 1, len(B)):
			if curr[j] == B[i]:
				yield (curr[:i] + curr[j] + curr[i + 1:j] + curr[i] + curr[j + 1:])


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		return self.recursion(A, B, {})

	def recursion(self, A: str, B: str, memo: dict) -> int:
		if A == '':
			return 0
		key = A + ',' + B
		if key in memo:
			return memo[key]
		if A[0] == B[0]:
			return self.recursion(A[1:], B[1:], memo)
		move = 100000
		for i in range(1, len(A)):
			if B[i] == A[0]:
				tempB = B[1:i] + B[0] + B[i + 1:]
				move = min(move, self.recursion(A[1:], tempB, memo))
		memo[key] = move + 1
		return 1 + move


class Solution:
	from collections import deque

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0

		def G(pat):
			for i in range(len(B) - 1):
				if pat[i] != B[i]:
					break
			ans = []
			for j in range(i + 1, len(B)):
				if pat[j] == B[i]:
					ans.append(pat[:i] + pat[j] + pat[i + 1:j] + pat[i] + pat[j + 1:])
			return ans
		Q = deque([])
		visited = set()
		visited.add(A)
		Q.append((0, A))
		while Q:
			(lv, pat) = Q.popleft()
			for new in G(pat):
				if new not in visited:
					visited.add(new)
					Q.append((lv + 1, new))
					if new == B:
						return lv + 1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		N = len(A)
		dq = deque([(A, 0)])
		cnt = 0
		seen = {A}
		while dq:
			length = len(dq)
			for _ in range(length):
				(a, idx) = dq.popleft()
				for i in range(idx, N):
					if a[i] != B[i]:
						break
				else:
					return cnt
				lst = list(a)
				for j in range(i + 1, N):
					if a[j] != B[j] and a[j] == B[i]:
						(lst[j], lst[i]) = (lst[i], lst[j])
						state = ''.join(lst)
						if state not in seen:
							seen.add(state)
							dq.append((state, i + 1))
						(lst[j], lst[i]) = (lst[i], lst[j])
						if a[i] == B[j]:
							break
			cnt += 1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		step_list = []
		A_list = []
		for i in range(len(A)):
			A_list.append(A[i])
		states = [[A_list.copy(), 0, 0]]
		while states != []:
			state = states.pop(0)
			indictor = 0
			for i in range(state[1], len(A_list)):
				if state[0][i] != B[i]:
					indictor = 1
					for j in range(i + 1, len(A_list)):
						if state[0][j] == B[i] and B[j] != state[0][j]:
							new_state = state[0].copy()
							(new_state[j], new_state[i]) = (new_state[i], new_state[j])
							states.append([new_state, i + 1, state[2] + 1])
							if B[j] == state[0][i]:
								break
					break
			if indictor == 0:
				step_list.append(state[2])
		return min(step_list)


class Solution:

	def kSimilarity2(self, A, B):

		def nei(x):
			i = 0
			while x[i] == B[i]:
				i += 1
			for j in range(i + 1, len(x)):
				if x[j] == B[i] and x[i] != x[j]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
		(q, seen) = (collections.deque([(A, 0)]), {A})
		while q:
			(x, d) = q.popleft()
			if x == B:
				return d
			for y in nei(x):
				if y not in seen:
					(seen.add(y), q.append((y, d + 1)))

	def kSimilarity(self, A: str, B: str) -> int:
		if A == B:
			return 0
		m = len(A)

		def getNeighbors(word):
			i = 0
			while word[i] == B[i]:
				i += 1
			for j in range(i + 1, m):
				if word[j] == B[i] and word[j] != word[i]:
					yield (word[:i] + word[j] + word[i + 1:j] + word[i] + word[j + 1:])
		visited = {A}
		queue = collections.deque([(A, 0)])
		while queue:
			(word, d) = queue.popleft()
			if word == B:
				return d
			for nbor in getNeighbors(word):
				if nbor not in visited:
					visited.add(nbor)
					queue.append((nbor, d + 1))


class Solution:

	def kSimilarity(self, A, B):
		n = len(A)

		def nei(x):
			i = 0
			while x[i] == B[i]:
				i += 1
			for j in range(i + 1, n):
				if x[j] == B[j]:
					continue
				if x[j] == B[i] and x[i] == B[j]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
					break
				if x[j] == B[i]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
		pool = [(A, 0)]
		seen = {A}
		for (x, d) in pool:
			if x == B:
				return d
			for y in nei(x):
				if y not in seen:
					seen.add(y)
					pool.append((y, d + 1))


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		mem = dict()

		def process(A, B):
			key = '%s_%s' % (A, B)
			if A == B:
				return 0
			if key in mem:
				return mem[key]
			if A[0] == B[0]:
				return process(A[1:], B[1:])
			c2 = float('inf')
			temp = list(B)
			for (idx, val) in enumerate(B):
				if val == A[0]:
					(temp[idx], temp[0]) = (temp[0], temp[idx])
					c2 = min(c2, 1 + process(A[1:], ''.join(temp)[1:]))
					(temp[0], temp[idx]) = (temp[idx], temp[0])
			mem[key] = c2
			return mem[key]
		return process(A, B)


from functools import lru_cache

class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		@lru_cache(None)
		def solve(s1, s2):
			if not s1:
				return 0
			if s1[0] == s2[0]:
				return solve(s1[1:], s2[1:])
			ans = 21
			for (i, c) in enumerate(s1):
				if s2[0] == c:
					ans = min(ans, 1 + solve(s1[1:i] + s1[0] + s1[i + 1:], s2[1:]))
			return ans
		return solve(A, B)


class Solution:

	def kSimilarity(self, A, B):

		def nei(x):
			i = 0
			while x[i] == B[i]:
				i += 1
			for j in range(i + 1, len(x)):
				if x[j] == B[i] and x[i] != x[j]:
					yield (x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:])
		(q, seen) = (collections.deque([(A, 0)]), {A})
		while q:
			(x, d) = q.popleft()
			print(x)
			if x == B:
				return d
			for y in nei(x):
				if y not in seen:
					(seen.add(y), q.append((y, d + 1)))


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		dic = {c: i for (i, c) in enumerate('abcdef')}
		bag = dict()
		stack = []
		for (a, b) in zip(A, B):
			if a != b:
				(i, j) = (dic[a], dic[b])
				bag[i, j] = bag.get((i, j), 0) + 1
				stack.append((i, j))
		output = 0

		def search(stack):
			if not stack:
				return 0
			(i, j) = stack.pop()
			if (j, i) in stack:
				idx = stack.index((j, i))
				stack = stack[:idx] + stack[idx + 1:]
				return search(stack) + 1
			else:
				best = float(inf)
				for (idx, pair) in enumerate(stack):
					if pair[0] == j:
						curr = search(stack[:idx] + [(i, pair[1])] + stack[idx + 1:]) + 1
						best = min(curr, best)
				return best
		return search(stack)


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		n = len(A)
		A = list(A)
		B = list(B)
		base = 0
		for i in range(n):
			if A[i] == B[i]:
				continue
			for j in range(i + 1, n):
				if A[i] == B[j] and A[j] == B[i]:
					(A[i], A[j]) = (A[j], A[i])
					base += 1
					break

		def dfs(i):
			if i == n:
				return 0
			if A[i] == B[i]:
				return dfs(i + 1)
			desired = B[i]
			cand = float('inf')
			for j in range(i + 1, n):
				if A[j] == desired:
					(A[i], A[j]) = (A[j], A[i])
					cand = min(cand, 1 + dfs(i + 1))
					(A[i], A[j]) = (A[j], A[i])
			return cand
		return base + dfs(0)


from collections import deque

class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		q = deque()
		q.append(A)
		visited = set([A])
		res = 0

		def neighbors(x):
			res = []
			i = 0
			while i < len(x) and x[i] == B[i]:
				i += 1
			for j in range(i + 1, len(A)):
				if x[j] == B[i]:
					new_str = x[:i] + x[j] + x[i + 1:j] + x[i] + x[j + 1:]
					if new_str not in visited:
						visited.add(new_str)
						res.append(new_str)
			return res
		while len(q) > 0:
			q_sz = len(q)
			for _ in range(q_sz):
				cur = q.popleft()
				if cur == B:
					return res
				for neighbor in neighbors(cur):
					q.append(neighbor)
			res += 1
		return res


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		queue = collections.deque([(A, 0, 0)])
		s = {A}
		while queue:
			(curr_A, curr_k, curr_p) = queue.popleft()
			if curr_A == B:
				return curr_k
			for i in range(curr_p, len(A)):
				if curr_A[i] != B[i]:
					for j in range(i + 1, len(A)):
						if curr_A[j] == B[i] and curr_A[:i] + curr_A[j] + curr_A[i + 1:j] + curr_A[i] + curr_A[j + 1:] not in s:
							queue.append((curr_A[:i] + curr_A[j] + curr_A[i + 1:j] + curr_A[i] + curr_A[j + 1:], curr_k + 1, i + 1))
							s.add(curr_A[:i] + curr_A[j] + curr_A[i + 1:j] + curr_A[i] + curr_A[j + 1:])
					break


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		queue = []
		queue.append((A, B, 0))
		step = len(A)
		minFlip = float('inf')
		seen = {(A, B): 0}
		while queue:
			(target, current, flip) = queue.pop(0)
			if seen[target, current] < flip:
				continue
			if target == current:
				minFlip = min(minFlip, flip)
				continue
			if target[0] == current[0]:
				temp = seen.get((target[1:], current[1:]), None)
				if not temp:
					seen[target[1:], current[1:]] = flip
				elif temp <= flip:
					continue
				seen[target[1:], current[1:]] = flip
				queue.append((target[1:], current[1:], flip))
			else:
				canni = [idx for (idx, char) in enumerate(current) if char == target[0]]
				piror = canni
				for loc in piror:
					lol = (target[1:], current[1:loc] + current[0] + current[loc + 1:])
					temp = seen.get(lol, None)
					if not temp:
						seen[lol] = flip + 1
					elif temp <= flip + 1:
						continue
					seen[lol] = flip + 1
					queue.append((target[1:], current[1:loc] + current[0] + current[loc + 1:], flip + 1))
		return minFlip


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:
		q = collections.deque()
		visited = set()
		q.append(A)
		visited.add(A)
		level = 0

		def getNext(S, B):
			S = list(S)
			res = []
			i = 0
			while i < len(S):
				if S[i] != B[i]:
					break
				i += 1
			for j in range(i + 1, len(S)):
				if S[j] == B[i]:
					(S[j], S[i]) = (S[i], S[j])
					res.append(''.join(S))
					(S[j], S[i]) = (S[i], S[j])
			return res
		while q:
			for _ in range(len(q)):
				curr = q.popleft()
				if curr == B:
					return level
				for next_str in getNext(curr, B):
					if next_str not in visited:
						q.append(next_str)
						visited.add(next_str)
			level += 1
		return -1


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def mk_similarities(s):
			for (i, c) in enumerate(B):
				if s[i] != c:
					break
			res = []
			for j in range(i + 1, len(B)):
				if s[j] == B[i]:
					ns = list(s)
					(ns[i], ns[j]) = (ns[j], ns[i])
					res.append(''.join(ns))
			return res
		N = len(A)
		ws = [A]
		swaps = 0
		seen = {A}
		while ws:
			nws = []
			for _ in range(len(ws)):
				s = ws.pop(0)
				if s == B:
					return swaps
				similarities = mk_similarities(s)
				for similarity in similarities:
					if similarity not in seen:
						nws.append(similarity)
						seen.add(similarity)
			ws = nws
			swaps += 1
		return None


class Solution:

	def kSimilarity(self, A: str, B: str) -> int:

		def getSwap(S):
			for (i, c) in enumerate(S):
				if c != B[i]:
					break
			T = list(S)
			for j in range(i + 1, len(S)):
				if S[j] == B[i]:
					(T[i], T[j]) = (T[j], T[i])
					yield ''.join(T)
					(T[j], T[i]) = (T[i], T[j])
		(queue, cnt) = ([A], {A: 0})
		while queue:
			S = queue[0]
			del queue[0]
			if S == B:
				return cnt[S]
			for T in getSwap(S):
				if T not in cnt:
					cnt[T] = cnt[S] + 1
					queue.append(T)