ধরুন আমাদের কাছে S এবং T দুটি স্ট্রিং আছে এগুলি ছোট হাতের অক্ষর দিয়ে গঠিত। S-তে কোনো অক্ষর একাধিকবার আসে না। S কে আগে কিছু কাস্টম ক্রমে সাজানো হয়েছিল। আমাদের T-এর অক্ষরগুলিকে পারমিউট করতে হবে যাতে তারা S সাজানো ক্রম অনুসারে মেলে। আরও নির্দিষ্টভাবে, যদি S-তে y-এর আগে x হয়, তাহলে ফিরে আসা স্ট্রিং-এ y-এর আগে x আসবে।
সুতরাং যদি S =“cba” এবং T =“abcd”, তাহলে আউটপুট হবে “cbad”। এখানে "a", "b", "c" S তে দেখা যাচ্ছে, তাই "a", "b", "c" এর ক্রম "c", "b", এবং "a" হতে হবে। যেহেতু "d" S-তে প্রদর্শিত হয় না, এটি T-এর যেকোনো অবস্থানে থাকতে পারে। "dcba", "cdba", "cbda"ও বৈধ আউটপুট।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
খালি স্ট্রিং হিসাবে ret সেট করুন
-
একটি মানচিত্র m সংজ্ঞায়িত করুন এবং T-এ উপস্থিত প্রতিটি অক্ষরের ফ্রিকোয়েন্সি m
এ সংরক্ষণ করুন -
i এর জন্য 0 থেকে S – 1
এর আকার-
x :=S[i]
-
j-এর জন্য 0 থেকে m[x] – 1
পরিসরে-
ret :=ret + x
-
-
m[x] :=0
-
-
প্রতিটি জোড়ার জন্য এটি m −
-
যদি এর মান হয়> 0, তাহলে
-
i এর জন্য রেঞ্জ 0 থেকে এর মান - 1
-
ret :=এটার ret concatenate কী
-
-
-
-
রিটার্ন রিটার্ন
উদাহরণ(C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string customSortString(string S, string T) {
string ret = "";
unordered_map <char, int> m;
for(int i = 0; i < T.size(); i++){
m[T[i]]++;
}
for(int i = 0; i < S.size(); i++){
char x = S[i];
for(int j = 0; j < m[x]; j++){
ret += x;
}
m[x] = 0;
}
unordered_map <char, int> :: iterator it = m.begin();
while(it != m.end()){
if(it->second > 0){
for(int i = 0; i < it->second; i++)ret += it->first;
}
it++;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.customSortString("cba", "abcd"));
} ইনপুট
"cba" "abcd"
আউটপুট
cbad
