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

{% hint style="info" %}
找最短距離的概念常可以用BFS的概念實現，要用到queue來達到BFS然後unordered\_set來紀錄已經搜尋過的中間結果。先找到當前這個string和目標string不一樣的char位置i，然後再從這個位置i往後找到位置j使得當前這個string的第j個位置上的char和目標string的第j個位置上的char不一樣，且目標string上的第j個char和當前string的第i個char一樣，就可以swap然後判斷沒搜尋過的話就能加入queue還有hashset中。這就像是一種greedy method找第一個不符合的char然後再找到不符合的char該放到哪。
{% endhint %}

```cpp
// BFS
int kSimilarity(string A, string B) {
    if (A == B) return 0;
    int res = 0, len = A.length();
    queue<string> q({A});
    unordered_set<string> visited({A});
    while (!q.empty()) {
        ++res;
        for (int k = q.size() - 1; k >= 0; --k) {
            string str = q.front(); q.pop();
            int i = 0;
            while (str[i] == B[i]) ++i;
            for (int j = i + 1; j < len; ++j) {
                if (str[j] == B[j] || str[i] != B[j]) continue; // Skip already sorted or unmatched 
                swap(str[i], str[j]);
                if (str == B) return res;
                if (!visited.count(str)) {
                    q.push(str);
                    visited.insert(str);
                }
                swap(str[i], str[j]); // reset
            }
        }
    }
    return res;
}
```

```cpp
// DFS Backtracking
int backtracking(string& A, const string& B, unordered_map<string, int>& mp, int i) {
    if (A == B) return 0;
    if (mp.count(A)) return mp[A];
    int res = INT_MAX;
    while (i < A.length() && A[i] == B[i]) ++i;
    for (int j = i + 1; j < A.length(); ++j) {
        if (A[j] == B[i]) {
            swap(A[i], A[j]);
            int next = backtracking(A, B, mp, i + 1);
            if (next != INT_MAX) {
                res = min(res, next + 1);
            }
            swap(A[i], A[j]);
        }
    }
    mp[A] = res;
    return res;
}
int kSimilarity(string A, string B) {
    unordered_map<string, int> mp;
    return backtracking(A, B, mp, 0);
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dfs-and-bfs/854.-k-similar-strings.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.