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.
Sample C++ Code using Breadth-First Search
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;
}
};