মান লিজিয়ে আমাদের একটি স্ট্রিং s দেওয়া আছে, এবং ইনডেক্সের জোড়ার একটি অ্যারে pairs যেখানে pairs[i] = [a, b] নির্দেশ করে স্ট্রিং-এর ২টি ইনডেক্স (0-ইন্ডেক্সড)। আমরা দেওয়া pairs-এ যেকোনো জোড়া ইনডেক্সের ক্যারেক্টার গুলো যেকোনো সংখ্যকবার স্ব্যাপ করতে পারি। আমাদের স্ব্যাপ ব্যবহার করে s কে যেটি লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোট স্ট্রিং-এ পরিবর্তন করা সম্ভব সেটি বের করতে হবে।
উদাহরণস্বরূপ, যদি ইনপুট হয় s = "dcab" এবং pairs = [[0,3], [1,2]], তবে আউটপুট হবে "bacd"। s[0] এবং s[3] এক্সচেঞ্জ করলে s = "bcad", তারপর s[1] এবং s[2] এক্সচেঞ্জ করলে s = "bacd"।
সমাধানের ধাপসমূহ
- n := অ্যারের সাইজ, parent := সাইজ n-এর একটি অ্যারে, এটিকে -1 দিয়ে ফিল করুন
- ret নামক একটি স্ট্রিং তৈরি করুন সাইজ n এবং এটিকে * দিয়ে ফিল করুন
- for i in range 0 to size of pairs:
- u := pairs[i, 0] এবং v := pairs[i, 1]
- যদি u এবং v-এর parent একই হয়, তবে পরবর্তী ইটারেশনে যান
- parent[parent of u] := parent of v
- arr1 নামক একটি অ্যারে ডিফাইন করুন সাইজ n
- for i in range 0 to n – 1: s[i] কে arr[parent of i]-তে ইনসার্ট করুন
- for i in range 0 to n – 1: arr[i] কে ডান পাশ থেকে পড়ে সর্ট করুন
- for i in range 0 to n – 1:
- ret[i] := arr1[parent of i]-এর শেষ এন্ট্রি
- arr1[parent of i]-এর শেষ নোড ডিলিট করুন
উদাহরণ (C++)
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন -
class Solution {
public:
vector <int> parent;
int getParent(int x){
if(parent[x] == -1) return x;
return parent[x] = getParent(parent[x]);
}
string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
int n = s.size();
parent = vector <int>(n, -1);
string ret(n, '*');
for(int i = 0; i < pairs.size(); i++){
int u = pairs[i][0];
int v = pairs[i][1];
if(getParent(u) == getParent(v)) continue;
parent[getParent(u)] = getParent(v);
}
vector < char > arr1[n];
for(int i = 0; i < n; i++){
arr1[getParent(i)].push_back(s[i]);
}
for(int i = 0; i < n; i++){
sort(arr1[i].rbegin(), arr1[i].rend());
}
for(int i = 0; i < n; i++){
ret[i] = arr1[getParent(i)].back();
arr1[getParent(i)].pop_back();
}
return ret;
}
};
ইনপুট
"dcab" [[0,3],[1,2]]
আউটপুট
"bacd"
