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