সমস্যা বিবরণ
দুটি স্ট্রিং A এবং B দেওয়া থাকলে। A-তে দুই ক্যারেক্টার সোয়াপ করে B বানাতে হলে K-সিমিলার বলা হয়। দুটি আনাগ্রাম A, B-এর জন্য ন্যূনতম K বের করতে হবে।
উদাহরণ
A = "abc", B = "bac" → আউটপুট = 1 (সোয়াপ: a ও b)
সমাধান পদ্ধতি
- BFS দিয়ে স্টেট স্পেস এক্সপ্লোর করা হয়।
- প্রতিটি স্টেটে প্রথম মিসম্যাচ পজিশন i বের করা হয়।
- i+1 থেকে j পর্যন্ত যেসব পজিশনে B[i] আছে এবং সেটি B[j] নয়, সেগুলো সোয়াপ করে নতুন স্টেট তৈরি করা হয়।
- ভিজিটেড সেট দিয়ে ডুপ্লিকেট এড়ানো হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
void swapp(string &s, int i, int j) {
char x = s[i], y = s[j];
s[i] = y; s[j] = x;
}
public:
int kSimilarity(string A, string B) {
if (A == B) return 0;
unordered_set<string> visited;
visited.insert(A);
queue<string> q;
q.push(A);
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
string curr = q.front(); q.pop();
int i = 0;
while (i < curr.size() && curr[i] == B[i]) i++;
for (int j = i + 1; j < curr.size(); j++) {
if (curr[i] == curr[j]) continue;
if (curr[j] != B[i]) continue;
if (curr[j] == B[j]) continue;
swapp(curr, i, j);
if (curr == B) return lvl;
if (!visited.count(curr)) {
visited.insert(curr);
q.push(curr);
}
swapp(curr, i, j);
}
}
}
return -1;
}
};
int main() {
Solution ob;
cout << ob.kSimilarity("abc", "bac");
return 0;
}ইনপুট ও আউটপুট
ইনপুট: "abc", "bac"
আউটপুট: 1
