K-Similar Strings

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. 1 <= A.length == B.length <= 20

2. A and B contain only lowercase letters from the set {'a', 'b', 'c', 'd', 'e', 'f'}

Solution:

class Solution {
    public int kSimilarity(String A, String B) {
        Queue<String> queue = new LinkedList<>();
        queue.add(A);

        Map<String, Integer> dist = new HashMap();
        dist.put(A, 0);

        while (!queue.isEmpty()) {
            String S = queue.poll();
            if (S.equals(B)) return dist.get(S);
            for (String T: neighbors(S, B)) {
                if (!dist.containsKey(T)) {
                    dist.put(T, dist.get(S) + 1);
                    queue.add(T);
                }
            }
        }

        return -1;
    }

    public List<String> neighbors(String S, String target) {
        List<String> ans = new ArrayList();
        int i = 0;
        while (S.charAt(i) == target.charAt(i)) i++;
        

        char[] T = S.toCharArray();
        for (int j = i+1; j < S.length(); ++j){
            if (S.charAt(j) == target.charAt(i)) {
                swap(T, i, j);
                ans.add(new String(T));
                swap(T, i, j);
            }
        }
        return ans;
    }

    public void swap(char[] T, int i, int j) {
        char tmp = T[i];
        T[i] = T[j];
        T[j] = tmp;
    }
}