สตริง K-คล้ายกันใน C++

คำอธิบายปัญหา

สตริง A, B เป็น K-similar ถ้าสลับตัวอักษรใน A ทั้งหมด K ครั้ง ได้ B (A, B เป็น anagram) หา K น้อยที่สุด

ตัวอย่าง

A="abc", B="bac" → Output: 1 (swap a,b)

แนวทางแก้ปัญหา: BFS + Pruning

1. BFS จาก A ระดับต่อระดับ (แต่ละระดับ = 1 swap)
2. Pruning สำคัญ: ที่ตำแหน่ง i แรกที่ A[i]≠B[i] ลองสลับกับ j>i ก็ต่อเมื่อ:
   • A[j] == B[i] (สลับแล้ว i จะถูกต้อง)
   • A[j] != B[j] (j ยังไม่ถูกต้อง ไม่อยากทำลาย)
   • A[i] != A[j] (กัน swap ตัวเดียวกัน)
3. ใช้ visited set ป้องกันซ้ำ

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    void swapp(string& s, int i, int j) {
        swap(s[i], s[j]);
    }
    
public:
    int kSimilarity(string A, string B) {
        if(A == B) return 0;
        unordered_set<string> visited{A};
        queue<string> q;
        q.push(A);
        
        for(int lvl=1; !q.empty(); lvl++) {
            int sz = q.size();
            while(sz--) {
                string cur = q.front(); q.pop();
                int i = 0;
                while(i < cur.size() && cur[i] == B[i]) i++;
                
                for(int j=i+1; j