> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/k-similar-strings.md).

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

```java
class Solution {
    public int kSimilarity(String A, String B) {
        char[] strB = B.toCharArray();
        Queue<String> q = new LinkedList<>();
        q.add(A);
        int count = 0;
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                char[] node = q.poll().toCharArray();
                int i = 0;
                while (i < strB.length && node[i] == strB[i])
                    i++;
                // If found match
                if (i == strB.length)
                    return count;
                for (int j = i + 1; j < node.length; j++) {
                    if (node[j] == strB[i]) {
                        swap(node, i, j);
                        q.add(new String(node));
                        swap(node, i, j);
                    }
                }
            }
            count++;
        }
        return -1;
    }

    public void swap(char[] str, int i, int j) {
        char t = str[i];
        str[i] = str[j];
        str[j] = t;
    }
}
```