# K-Similar Strings Problem

## Description

LeetCode Problem 854.

Strings s1 and s2 are k-similar (for some non-negative integer k) if we can swap the positions of two letters in s1 exactly k times so that the resulting string equals s2.

Given two anagrams s1 and s2, return the smallest k for which s1 and s2 are k-similar.

Example 1:

``````1
2
Input: s1 = "ab", s2 = "ba"
Output: 1
``````

Example 2:

``````1
2
Input: s1 = "abc", s2 = "bca"
Output: 2
``````

Example 3:

``````1
2
Input: s1 = "abac", s2 = "baca"
Output: 2
``````

Example 4:

``````1
2
Input: s1 = "aabc", s2 = "abca"
Output: 2
``````

Constraints:

• 1 <= s1.length <= 20
• s2.length == s1.length
• s1 and s2 contain only lowercase letters from the set {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’}.
• s2 is an anagram of s1.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
int kSimilarity(string A, string B) {
if (A == B) return 0;

unordered_set<string> visit;
queue<pair<string, int>> q;

int n = A.size();
int step = 0;

int i = 0;
for (; i < n; ++i) {
if (A[i] != B[i]) break;
}

q.push({A, i});
visit.insert(A);

while (!q.empty()) {
int size = q.size();

for (int i = 0; i < size; ++i) {
string t = move(q.front().first);
int index = q.front().second;
q.pop();

if (t == B) return step;

while (t[index] == B[index]) ++index;
for (int i = index + 1; i < n; ++i) {
if (t[i] == B[index] && t[i] != B[i]) {
swap(t[index], t[i]);

if (visit.count(t) == 0) {
q.push({t, index+1});
visit.insert(t);
}

swap(t[index], t[i]);
}
}
}
++step;
}

return step;
}
};
``````