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'}

Difficulty: interview

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

# class Solution:
#     def kSimilarity(self, A: str, B: str) -> int:
#         n = len(A)
#         A, B = list(A), list(B)
#         mp = defaultdict(list)
#         for i, ch in enumerate(A):
#             mp[ch].append(i)
#         def dfs(idx):
#             if idx == n:
#                 return 0
#             if A[idx] == B[idx]:
#                 return dfs(idx+1)
#             res = float('inf')
#             for nxt in range(idx+1,n):
#                 if A[nxt] != B[idx]:
#                     continue
#                 A[idx], A[nxt] = A[nxt], A[idx]
#                 res = min(res, dfs(idx+1)+1)
#                 A[idx], A[nxt] = A[nxt], A[idx]
#             return res
#         return dfs(0)

from functools import lru_cache
class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        n = len(A)
        # mp = defaultdict(list)
        # for i, ch in enumerate(A):
        #     mp[ch].append(i)
        @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]:
                # if s[nxt] != B[idx] or s[nxt] == B[nxt]:
                    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):   # takes O(N)
                    if next in visited:
                        continue
                    q.append(next)
                    visited.add(next)
                
    def _swap(self, s, B):    # now only takes O(N)
        i = 0
        while s[i] == B[i]:   # if S[i]==B[i], we don't need to swap them - strong prune to makes sure swapped string always get more and more similar with B
            i += 1
        for j in range(i + 1, len(s)):
            if s[j] == B[i]:  # since B[i]!=s[i], if we swap s[j] to s[i], now B[i]=s[i]: this is how every swap make sure we get more and more closer to B
                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:]

        # def test():
        stack = [(A, 0)]
        visit = {A}
        for cur, d in stack:
            # cur, d = stack.pop()
            if cur == B: return d
            for neighbor in nei(cur):
                if neighbor not in visit:
                    visit.add(neighbor)
                    stack.append((neighbor, d+1))
                    
        
        # 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:
    # Just like the shuffle board game, consider each string as a node
    # And for each child is the shuffled result
    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)
        
        
        # ans = 0
        # for i in range(n):
        #     if A[i]==B[i]:
        #         continue
        #     else:
        #         ans+=1
        #         for j in range(i+1, n):
        #             if B[j] == A[i]:
        #                 B[i], B[j] = B[j], B[i]
        #                 break
        # return ans
        
        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)
                        

#         ans = 0
#         for i in range(n):
#             if A[i]==B[i]:
#                 continue
#             else:
#                 ans+=1
#                 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]
#                         break
#         return ans
                        

        
#         def rec(i):
#             if i==n:
#                 return 0
            
#             if A[i]==B[i]:
#                 return rec(i+1)
#             else:
#                 min_ = sys.maxsize
#                 j = 0
#                 while A[j]==B[j]:
#                     j+=1
#                 for k in range(j+1, n):
#                     if B[k] == A[j]:
#                         B[j], B[k] = B[k], B[j]
#                         min_ = min(min_, rec(i+1) + 1)
#                         B[j], B[k] = B[k], B[j]
#                 return min_
        
#         return rec(0)
#         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)], set([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))


'''
'ab'
'ba'
1

'abc' -> 'acb' -> 'bca'
'bca'
2

'abac' -> 'baac' -> 'baca'
'baca'
2

'aabc' -> 'acba' -> 'abca'
'abca'
2

* See the problem as a graph problem.
* Nodes are the strings.
* Two nodes are conneted to each order if the one string is equal to the
  other if we swap two chars.
* The problem boils down to find the shortest path between A and B.
* Since this is an unweigthed graph, the shortest path can be found by
  traversing the graph in BFS.
  
  
'abc' -> 'bac'
      -> 'cba'
      -> 'acb'
      
* This approach doesn't sound an efficient approach because for every node
  we'd need to generated its adjcent nodes.
  
* This sounds like an optimization problem.

'abcd'  --> 'bcd'
'adbc'      'dbc'

* If the first char from A and B are equal, recurse on the remaining string.
* Else, swap A so it first char match and recurse. If the target char repeats,
  try swapping all of them and consider the one that leads to the smallest K.
  
  
('abac', 'baca') = 1 + ('aac', 'aca')
('aac', 'aca') = ('ac', 'ca')
('ac', 'ca') = 1 + ('a', 'a')
('a', 'a') = 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])

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
            ans = []
            for j in range(i, len(s)):
                if s[j] == B[i]:
                    ans.append(s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:])
            return ans
        
        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 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:
    # Just like the shuffle board game, consider each string as a node
    # And for each child is the shuffled result which one step closer to the target
    # Another key is how to find the next step (by finding the first different letter and swap)
    # The order does not matter
    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:
        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)
                
                    # if len(poss) > 1:
                    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
                    # else:
                    #     if poss:
                    #         # print(A,B, a,b)
                    #         swap(left,poss[0])
                    #         swaps += 1 

                left = (left+1) % len(A)
                right= (right+1) % len(B)
            
            return swaps

#         left = right = 0
#         ok = True
#         swaps = 0
#         while A != B:
#             ok = False
#             a = A[left]
#             b = B[right]
            
#             if a != b:
#                 # indx = A.index(b)
#                 for i,c in enumerate(A):
#                     if b == c and i >= left:
#                         indx = i
#                         break
#                 swap(left,indx)
#                 swaps += 1
            
#             left = (left+1) % len(A)
#             right= (right+1) % len(B)
        
        f = helper(0,0, tuple(A+B))
        print(A)
        print(B)
            
        # out = helper(A, 0, 0)
        # print(out)
        return f
                


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)
                
                    # if len(poss) > 1:
                    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))
        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):
            # count number of differing characters
            return sum( (1 if c!=d else 0 for (c,d) in zip(a,b) ) )

        def swap(s, i, j):
            # swap ith and jth chars of string s
            # assert 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):
            # can string be swapped into problem's str `A` in `k` moves?
            if string == A:
                return True
            if k == 0:
                return False
            for i,c in enumerate(string):
                if A[i] == c:
                    continue
                # c is wrong, we need to swap a correct letter into it
                # only look for after current position to avoid double swaps
                for j in range(i, len(A)):
                    if string[j] == A[i] and A[j] != A[i]:
                        # try this swap
                        if DFS(swap(string, i, j), k-1):
                               return True
                # return False after trying to correct the first wrong letter:
                # if there is any `k` solution, then there's a `k` solution
                # that starts on this letter
                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:
        A, B = list(A), list(B)
        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[:]
                    candidate[i], candidate[j] = candidate[j], candidate[i]
                    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)
                #print(f'cur={cur}, first={first}')
                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]
                            #print(f'B={B}')
                            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:
        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 = list(v)
                    candidate[i], candidate[j] = candidate[j], candidate[i]
                    candidate = ''.join(candidate)
                    q.append((cnt+1, candidate, i+1))


class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        self.N = len(A)
        self.dict1 = collections.defaultdict()
        return self.dfs(list(A), list(B), 0)
                
    
    def dfs(self,A, B, pos):
        sB = ''.join(B)
        if sB in self.dict1:
            return self.dict1[sB]
            
        if A == B:
            return 0
            
        while A[pos] == B[pos]:
            pos += 1
                
        minCnt = float('inf')
        for i in range(pos + 1, self.N):
            if B[i] == A[pos] and B[i] != A[i]:
                B[i], B[pos] = B[pos], B[i]
                tmp = self.dfs(A, B, pos + 1) + 1
                minCnt = min(tmp, minCnt)
                B[i], B[pos] = B[pos], B[i]
                    
        self.dict1[sB] = minCnt
        return minCnt


class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        def dist(a, b):
            # count number of differing characters
            return sum( (1 if c!=d else 0 for (c,d) in zip(a,b) ) )

        def swap(s, i, j):
            # swap ith and jth chars of string s
            # assert 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):
            # print(f\"  {string}\")
            if string in seen:
                return False, 0
            seen.add(string)
            # print(f\"   {k}:   {string}\")
            # can string be swapped into problem's str `A` in `k` moves?
            if string == A:
                return True, 1

            # early break if distance is too great:
            # best possible for string of length N:
            #    N is even: N/2  (every swap corrects 2 letters
            #    N is odd: N//2 + 1
            #      every swap until last 3 letters corrects 2
            #      last 3 letters take 2 swaps
            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
                # c is wrong, we need to swap a correct letter into it
                # only look for after current position to avoid double swaps
                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):
        # for k in range(len(A)):
            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]):            #Move forward when elements of A and B are equal
                    if e[0][y] == A[y]:
                        y += 1
                    else:
                        break
                if y == len(e[0]):               #If everything is equal return level
                    return l
                else:
                    nei = find_neighbors(e[0], y)       #Find all A[i]'s to the right of B which are prospective candidates
                    for n in nei:
                        new_e = e[0][:]
                        new_e[n] = e[0][y]            #Swap A[i] with all matched neighbors(Generating a new 'state')
                        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 bfs(self, A: str, B: str):
        if A == B: return 0
        n = len(A)
        q = []
        # visited = [False for i in range(n)]
        q.append((B, 0, 0))
        while q:
            processed, idx, swaps = q.pop(0)
            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
                    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 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)] # (i) index, (k) swaps made, (B) current list
        
        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
            
            


from collections import deque
class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        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]):            #Move forward when elements of A and B are equal
                    if e[0][y] == A[y]:
                        y += 1
                    else:
                        break
                if y == len(e[0]):               #If everything is equal return level
                    return l
                else:
                    nei = find_neighbors(e[0], y)       #Find all A[i]'s to the right of B which are prospective candidates
                    for n in nei:
                        new_e = e[0][:]
                        new_e[n] = e[0][y]            #Swap A[i] with all matched neighbors(Generating a new 'state')
                        q.append([new_e, y + 1])
            l += 1
        return l

class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        def dist(a, b):
            # count number of differing characters
            return sum( (1 if c!=d else 0 for (c,d) in zip(a,b) ) )

        def find_wrong_letters(working):
            # given a working string, return two dicts that track work to be done:
            #   (wants, wrongs)
            # `wants[target]` maps to set of positions that need `target` letter
            # `wrongs[letter]` maps to set positions that have a wrong `letter`
            #     if i in wants{target] and j in wrongs[letter]
            #       we can swap ith and jth letters to improve 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 number of wrong letters
            # assume a perfect scenario:
            #    each swap fixes two letters
            count = dist(string, A)
            return count/2 if count % 2 == 0 else count//2 + 1

        def swap(s, i, j):
            # swap ith and jth chars of string s
            # assert 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] )

        # print(A)
        # print(B)
        # print(\"0123456789abcdefghijklmnopqrst\"[:len(A)])
        # needs, wrongs = find_wrong_letters(B)
        # print(f\"wrong: {wrongs}\")
        # print(f\"needs: {needs}\")
        # return 0

        if A == B:
            return 0
        # BFS
        # q is a heap that holds triples:
        #   (estimate, swap_count_so_far, the_working_string)
        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, 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]):            #Move forward when elements of A and B are equal
                    if e[0][y] == A[y]:
                        y += 1
                    else:
                        break
                if y == len(e[0]):               #If everything is equal return level
                    return l
                else:
                    nei = find_neighbors(e[0], y)       #Find all A[i]'s to the right of B which are prospective candidates
                    for n in nei:
                        new_e = e[0][:]
                        new_e[n] = e[0][y]            #Swap A[i] with all matched neighbors(Generating a new 'state')
                        q.append([new_e, y + 1])
            l += 1
        return l

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:
        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 = 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:
        #assert(len(A) == len(B))
        #assert(sorted(A) == sorted(B))
        
        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

class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        def nei(x):
            i = 0
            while x[i] == B[i]: i+=1 #continue incremeneting if characters are same
            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:] #swaps the two characters
        q, seen = [(A,0)], {A}

        while q != []:
            x, d = q.pop(0)
            if x == B: return d #return immediately from BFS if the strings are the same
            for y in nei(x):
                #print(\"y\", y)
                if y not in seen:
                    seen.add(y), q.append((y,d+1))
            #print(\"q\", q)


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 
                        else:
                            if 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:
        '''
        A classic BFS solution to find the shortest path;
        The neighbors to each node string S are all the strings reachable with 1 swap, that match the first unmatched character in S.
        '''
        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):
            # count number of differing characters
            return sum( (1 if c!=d else 0 for (c,d) in zip(a,b) ) )

        def find_wrong_letters(working):
            # given a working string, return two dicts that track work to be done:
            #   (wants, wrongs)
            # `wants[target]` maps to set of positions that need `target` letter
            # `wrongs[letter]` maps to set positions that have a wrong `letter`
            #     if i in wants{target] and j in wrongs[letter]
            #       we can swap ith and jth letters to improve 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):
            # swap ith and jth chars of string s
            # assert 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] )

        # greedy BFS
        #    only search
        # q holds triples:
        #   (estimate, swap_count_so_far, the_working_string)
        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)
                # improvement = 2
                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:
        # BFS
        # Key: at every step, we swap and make sure we put one char at correct pos, BFS makes sure it's shortest
        
        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):
                    # Key: NOT (cur[j] == B[i] or cur[i] == B[j])!!! Because in each BFS level we only need to make sure i pos can be corrected by swap(i,j), in the next level, since range of i and j is decreasing, width of BFS won't too large.
                    # But cur[i]==B[j] NOT guarantee i pos is corrected, next level it might still starts from i, thus range of search is width and got TLE
                    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:
    @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 B[i]==A[0] and A[i]==B[0]: 
                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 B[i]==A[0]: ans = min(ans, 1+self.kSimilarity(A[1:],B[1:i]+B[0]+B[i+1:]))
        return ans

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] and string[j] != B[j]:
                    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:
#     def kSimilarity(self, A: str, B: str) -> int:
#         n = len(A)
#         A, B = list(A), list(B)
#         mp = defaultdict(list)
#         for i, ch in enumerate(A):
#             mp[ch].append(i)
#         def dfs(idx):
#             if idx == n:
#                 return 0
#             if A[idx] == B[idx]:
#                 return dfs(idx+1)
#             res = float('inf')
#             for nxt in range(idx+1,n):
#                 if A[nxt] != B[idx]:
#                     continue
#                 A[idx], A[nxt] = A[nxt], A[idx]
#                 res = min(res, dfs(idx+1)+1)
#                 A[idx], A[nxt] = A[nxt], A[idx]
#             return res
#         return dfs(0)

from functools import lru_cache
class Solution:
    def kSimilarity(self, A: str, B: str) -> int:
        n = len(A)
        # mp = defaultdict(list)
        # for i, ch in enumerate(A):
        #     mp[ch].append(i)
        @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] or s[nxt] == B[nxt]:
                    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:
        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:
        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:]
        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))

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)):
                # need to find one where curr[i] == goal[0] and goal[i] == curr[0]
                if curr[i] == goal[0] and goal[i] == curr[0]:
                    work = i
                    break
            if work:
                # only swap this one
                # remove 0 and work from the unmatched list
                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
        dq = deque([(A,0)])
        cnt = 0
        N = len(A)
        seen = set()
        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
                                if temp not in seen:
                                    seen.add(temp)
                                    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:
        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:

        def dist(a, b):
            # count number of differing characters
            return sum( (1 if c!=d else 0 for (c,d) in zip(a,b) ) )

        def estimate_remaining(string):
            # count number of wrong letters
            # assume a perfect scenario:
            #    each swap corrects two letters
            count = dist(string, A)
            return count/2 if count % 2 == 0 else count//2 + 1

        def find_wrong_letters(working):
            # given a working string, return two dicts that track work to be done:
            #   (wants, wrongs)
            # `wants[target]` maps to set of positions that need `target` letter
            # `wrongs[letter]` maps to set positions that have a wrong `letter`
            #     if i in wants{target] and j in wrongs[letter]
            #       we can swap ith and jth letters to improve 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):
            # swap ith and jth chars of string s
            # assert 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] )

        # BFS
        # q is a heap that holds triples:
        #   (estimate, swap_count_so_far, the_working_string)
        # q = deque()
        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:
        # 根据最后一位是否相等进行贪心的求解。dfs深搜
        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]:   
                        # 切记当前位置的ab不能对应相等，要不然肯定多操作了。
                        a_new = a[:i] + a[-1] + a[i + 1:-1]  #把a[i]与a[-1]交换了
                        res = min(res, 1 + helper(a_new, b[:-1]))
            memo[(a, b)] = res
            return res
        return helper(A, B)
        '''
        # 这道题虽然是hard但是通过你理解题意，很容易找到潜在的解答方法。
        # 第一重思路就是看到最小。那么只要比最小的大都OK，那么很容易想到用二分法去猜测答案。但是如何check存疑
        # 第二重思路就是看到两个node。第一个node通过交换变成第二个。交换的可能性很多。因此可以看乘bfs
        # BFS就是给你一个起点一个终点，问你最近的距离，最少的方式等等是多少！
        # by build directed edges bfs to find k
        def neighbor(x):
            i = 0
            while x[i] == B[i]:  # 更换的种类很多种，但是仍然需要剪枝无效的。因此相同部分就不改变了。
                i += 1
            for j in range(i + 1, len(x)): # 找到第一个不同的地方，然后去找可以过来填坑的letter
                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 neighbor(x):
                if y not in seen:
                    seen.add(y)
                    q.append((y, 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)):
                # need to find one where curr[i] == goal[0] and goal[i] == curr[0]
                if curr[i] == goal[0] and goal[i] == curr[0]:
                    work = i
                    break
            if work:
                # only swap this one
                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:]
        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))

class Solution:
    # save the indices of letters that are in the right place
    # create array 'correct' where the index corresponds to the letter in A and the value is the correct index
    # find every letter pair --> a pair is two letters in B that when swapped, will end up in the correct index
    # dynamic programming? number of displaced letters --> min # of swaps
    # subproblem = number of displaced letters
    # at most 20 swaps
    def kSimilarity(self, A: str, B: str) -> int:
        q, visited = [(A,0)], {A}
        # BFS
        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()
            #if pat==B:
            #    return lv
            
            for new in G(pat):
                if new not in visited:
                    visited.add(new)
                    Q.append((lv+1,new))
                    if new == B:
                        return lv+1
            
            #print(Q,visited)
            
        


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:
        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:
    @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:])
        ans = math.inf
        for i in range(1,len(B)): 
            if B[i]==A[0]: 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
        step_list = []
        A_list = []
        for i in range(len(A)):
            A_list.append(A[i])

        states = [[A_list.copy(),0,0],] #list, index, step
        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:
    @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:])
        
        ans = math.inf
        for i in range(1,len(B)):
            if B[i]==A[0]: ans = min(ans, 1+self.kSimilarity(A[1:],B[1:i]+B[0]+B[i+1:]))
        return ans
            


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



#         # def test():
#         stack = [(A, 0)]
#         visit = {A}
#         while stack:
#             cur, d = stack.pop()
#             if cur == B: return d
#             for neighbor in nei(cur):
#                 if neighbor not in visit:
#                     visit.add(neighbor)
#                     stack.append((neighbor, d+1))
                    
        
        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: 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
                #print(self._swap(curr, B))
                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
        if s[i]!=B[i]:
            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(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:
        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],] #list, index, step
        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] and B[j] == state[0][i]:
                            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])
                            break
                        elif 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])
                    break
            if indictor == 0:
                step_list.append(state[2])
        return min(step_list)



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
        
        # @lru_cache(maxsize=None)
        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
            
        # invariant: A[:i] == B[:i]
        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:
        ## check official solution and 
        ## https://leetcode.com/problems/k-similar-strings/discuss/269517/Python-Graph-BFS
        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()
            # print(curr_A, curr_k, curr_p)
            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 = 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
                else:
                    if 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
                #piror = [(loc, target[loc] == current[0]) for loc in canni]
                #piror.sort(key=lambda x:x[1],reverse = True)
                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
                    else:
                        if 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:
        def dist(a, b):
            # count number of differing characters
            return sum( (1 if c!=d else 0 for (c,d) in zip(a,b) ) )

        def swap(s, i, j):
            # swap ith and jth chars of string s
            # assert 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):
            # can string be swapped into problem's str `A` in `k` moves?
            if string == A:
                return True
            if k == 0:
                return False

            # early break if distance is too great:
            # best possible for string of length N:
            #    N is even: N/2  (every swap corrects 2 letters
            #    N is odd: N//2 + 1
            #      every swap until last 3 letters corrects 2
            #      last 3 letters take 2 swaps
            distance = dist(string, A)
            best = distance/2 if distance % 2 == 0 else (distance//2) + 1
            if k < best:
                return False

            for i,c in enumerate(string):
                if A[i] == c:
                    continue
                # c is wrong, we need to swap a correct letter into it
                # only look for after current position to avoid double swaps
                for j in range(i, len(A)):
                    if string[j] == A[i] and A[j] != A[i]:
                        # try this swap
                        if DFS(swap(string, i, j), k-1):
                               return True
                # return False after trying  the first wrong letter (because of trick):
                # if there is any `k` solution, then there's a `k` solution
                # that starts on this letter
                return False

        for k in range(len(A)):
            if DFS(B, k):
                return k



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): # len(s) == len(B)
            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)
                # print(s)
                if s == B:
                    return swaps
                similarities = mk_similarities(s)
                # print(similarities)
                for similarity in similarities:
                    if similarity not in seen:
                        nws.append(similarity)
                        seen.add(similarity)
            ws = nws
            swaps += 1
        return None

#         swaps = 0
#         N = len(A)
#         A = list(A)
#         for i, c in enumerate(B):
#             if A[i] == c:
#                 pass
#             else:
#                 nearest_c = None
#                 for j in range(i + 1, N):
#                     if A[j] == c:
#                         nearest_c = j
#                         break
#                 if nearest_c is None:
#                     return None
#                 else:
#                     A[i], A[j] = A[j], A[i]
#                     swaps += 1
#         return swaps
            
            
                


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}  # 初始化队列，cnt用于记录当前结点已经走了多少步
        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)

class Solution:
     def kSimilarity(self, A: str, B: str) -> int:
        def mk_similarities(s): # len(s) == len(B)
            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)
                # print(s)
                if s == B:
                    return swaps
                similarities = mk_similarities(s)
                # print(similarities)
                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:
        @lru_cache(None)
        def nei(x):
            i = 0
            while i < len(x) and x[i] == B[i]: i+=1
            res = []
            for j in range(i+1, len(x)):
                if x[j] == B[i]: 
                    res.append(x[:i]+x[j]+x[i+1:j]+x[i]+x[j+1:])
            return res
        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))

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