solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

class Solution {
   public:
    int kSimilarity(string s1, string s2) {
        queue<string> Q;
        unordered_map<string, int> d;

        Q.push({s1, 0});
        d[s1] = 0;

        int n = s1.size();
        while (!Q.empty()) {
            auto s = Q.front();
            Q.pop();
            if (s == s2) return d[s];
            int idx = 0;
            while (s[idx] == s2[idx]) idx++;

            for (int i = idx + 1; i < n; i++) {
                if (s[i] == s2[idx]) {
                    string tmp = s;
                    swap(tmp[i], tmp[idx]);
                    if (d.count(tmp) == 0) {
                        d[tmp] = d[s] + 1;
                        Q.push(tmp);
                    }
                }
            }
        }
        return -1;
    }
};