在C++中寻找K-Similar字符串的K值的程序

1. 什么是K-Similar字符串

K-Similar字符串是指将原字符串中最少的K个字符交换位置，使其成为目标字符串。例如，对于原字符串“abcbca”和目标字符串“abcabc”，将原字符串中的第2个和第4个字符交换位置，将原字符串中的第3个和第6个字符交换位置，就可以得到目标字符串。

2. 解决方案

我们可以使用BFS（Breadth-First-Search）算法来求解。首先，我们从目标字符串开始，将其加入队列中；然后，不断将队列中的字符串取出，并进行以下操作：

找到最左边不相等的字符；
将其与所有与它不相等的字符进行交换（因为存在K-Similar字符串，所以必然有这样的字符）；
判断交换后的字符串是否为目标字符串；
若是，则返回交换次数；否则，将交换后的字符串加入队列中。

代码如下：

int kSimilarity(string A, string B) {
    queue<string> q{{B}};
    unordered_set<string> visited{B};
    int res = 0;
    while (!q.empty()) {
        for (int size = q.size(); size > 0; --size) {
            string s = q.front();
            q.pop();
            if (s == A) return res;
            int i = 0;
            while (s[i] == A[i]) ++i;
            for (int j = i + 1; j < s.size(); ++j) {
                if (s[j] == A[i] && s[j] != A[j]) {
                    swap(s[i], s[j]);
                    if (visited.count(s)) swap(s[i], s[j]);
                    else {
                        visited.insert(s);
                        q.push(s);
                        swap(s[i], s[j]);
                    }
                }
            }
        }
        ++res;
    }
    return res;
}