ধরুন আমাদের কাছে সমান দৈর্ঘ্যের দুটি স্ট্রিং s1 এবং s2 রয়েছে যাতে শুধুমাত্র "x" এবং "y" অক্ষর থাকে। আমাদের কাজ হল এই দুটি স্ট্রিংকে একে অপরের সমান করা। আমরা যেকোন দুটি অক্ষরকে অদলবদল করতে পারি যা বিভিন্ন স্ট্রিং এর অন্তর্গত, যার মানে হল − s1[i] এবং s2[j] swap। আমাদের s1 এবং s2 সমান করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অদলবদল খুঁজে বের করতে হবে, অথবা যদি এটি করা অসম্ভব হয় তবে -1 ফেরত দিতে হবে। সুতরাং স্ট্রিংগুলো যদি s1 =“xy” এবং s2 =“yx” হয়, তাহলে আউটপুট হবে 2। যদি আমরা s1[0] এবং s2[0], s1 ="yy", s2 ="xx" অদলবদল করি। তারপর s1[0] এবং s2[1], s1 ="xy", s2 ="xy" অদলবদল করুন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- x1, x2, y1 এবং y2 কে 0 হিসাবে সেট করুন
- আমি 0 থেকে s1
- এর পরিসরে
- a :=s1[i] এবং b :=s2[i]
- যদি a এবং b এর সমান না হয়, তাহলে
- যদি a ='x' তাহলে x1 বাড়ান, অন্যথায় y1 বাড়ান 1
- যদি b =‘x’ তাহলে x2 বাড়ান, অন্যথায় y2 বাড়ান 1
- যদি (x1 + x2) বিজোড় হয় বা (y1 + y2) বিজোড় হয়, তাহলে -1 ফেরত দিন
- রিটার্ন x1/2 + y1/2 + (x1 মোড 2) * 2
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimumSwap(string s1, string s2) {
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
for(int i = 0; i < s1.size(); i++){
char a = s1[i];
char b = s2[i];
if(a != b){
if(a == 'x')x1++;
else y1++;
if(b == 'x')x2++;
else y2++;
}
}
if ((x1 + x2) & 1 || (y1 + y2) & 1)return -1;
return x1/2 + y1/2 + (x1 % 2) * 2;
}
};
main(){
Solution ob;
cout <<ob.minimumSwap("xy", "yx");
} ইনপুট
"xy" "yx"
আউটপুট
2
