## Algorithm

Problem Name: 854. K-Similar Strings

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:

```Input: s1 = "ab", s2 = "ba"
Output: 1
Explanation: The two string are 1-similar because we can use one swap to change s1 to s2: "ab" --> "ba".
```

Example 2:

```Input: s1 = "abc", s2 = "bca"
Output: 2
Explanation: The two strings are 2-similar because we can use two swaps to change s1 to s2: "abc" --> "bac" --> "bca".
```

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`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const kSimilarity = function(A, B) {
if (A === B) return 0
let arr = [[B, 0]]
while (arr.length > 0) {
let len = arr.length
for (let i = 0; i < len; i++) {
let [cur, step] = arr.shift()
for (let i = 0; i < cur.length; i++) {
if (cur[i] === A[i]) continue
for (let j = i + 1; j < cur.length; j++) {
if (cur[j] !== A[i]) continue
let newStr =
cur.substring(0, i) +
cur[j] +
cur.substring(i + 1, j) +
cur[i] +
cur.substring(j + 1)
if (newStr === A) return step + 1
if (cur[i] === A[j]) arr.unshift([newStr, step + 1])
else arr.push([newStr, step + 1])
}
break
}
}
}
}
``````
Copy The Code &

Input

cmd
s1 = "ab", s2 = "ba"

Output

cmd
1

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def kSimilarity(self, A, B):
b, n, k, stack = [c for c in B], len(A), float("inf"), [(0, 0, [c for c in A])]
while stack:
i, cnt, s = stack.pop()
while i < n and s[i] == b[i]:
i += 1
if i == n:
if cnt < k:
k = cnt
else:
for j in range(i + 1, n):
if s[j] == b[i] and s[j] != b[j]:
ls = s[:]
ls[i], ls[j] = ls[j], ls[i]
stack.append((i + 1, cnt + 1, ls))
return k
``````
Copy The Code &

Input

cmd
s1 = "ab", s2 = "ba"

Output

cmd
1