মনে করুন `s1` এবং `s2` নামে সমান দৈর্ঘ্যের দুটি স্ট্রিং আছে যেগুলো শুধু "x" এবং "y" অক্ষর থেকে বানানো। আমাদের এই দুটি স্ট্রিংকে একে অপরের সমান করতে হবে। আমরা যেকোনো দুটি ক্যারেক্টার সোয়াপ করতে পারি যা আলাদা স্ট্রিংয়ে অবস্থিত, অর্থাৎ - `s1[i]` এবং `s2[j]` সোয়াপ করা যাবে। আমাদের `s1` এবং `s2` সমান করার জন্য ন্যূনতম সোয়াপের সংখ্যা বের করতে হবে, অথবা -1 রিটার্ন করুন যদি অসম্ভব হয়। যদি স্ট্রিংগুলো `s1 = "xy"` এবং `s2 = "yx"` হয়, তবে আউটপুট হবে ২। যদি আমরা `s1[0]` এবং `s2[0]` সোয়াপ করি, `s1 = "yy"`, `s2 = "xx"`। তারপর `s1[0]` এবং `s2[1]` সোয়াপ করি, `s1 = "xy"`, `s2 = "xy"`।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- `x1`, `x2`, `y1` এবং `y2`-কে 0 সেট করুন
- `i` = 0 থেকে `s1`-এর আকার পর্যন্ত
- `a := s1[i]` এবং `b := s2[i]`
- যদি `a` এবং `b` এক নয়, তবে
- যদি `a = 'x'` তবে `x1` বাড়ান, অন্যথায় `y1` ১ বাড়ান
- যদি `b = 'x'` তবে `x2` বাড়ান, অন্যথায় `y2` ১ বাড়ান
- যদি `(x1 + x2)` অড্ড হয় অথবা `(y1 + y2)` অড্ড হয়, তবে -1 রিটার্ন করুন
- `x1/2 + y1/2 + (x1 mod 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
