import collections

class Solution:

    def find_first_mismatch(self, A, B):
        for i in range(len(A)):
            if A[i] != B[i]:
                return i

    def find_candidates(self, A, B, mismatch):
        for i in range(mismatch + 1, len(A)):
            if A[i] != B[i] and A[i] == B[mismatch]:
                yield Solution.swap(A, mismatch, i)

    def swap(A, i, j):
        chars = list(A)
        chars[i], chars[j] = chars[j], chars[i]
        return "".join(chars)

    def k_similarity(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """
        q = collections.deque([A])
        distance = 0
        seen = set([A])
        while q:
            for _ in range(len(q)):
                current = q.pop()
                if current == B:
                    return distance
                mismatch = self.find_first_mismatch(current, B)
                for candidate in self.find_candidates(current, B, mismatch):
                    if candidate not in seen:
                        seen.add(candidate)
                        q.appendleft(candidate)
            distance += 1

Input: A = "ab", B = "ba"
Output: 1

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

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

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