मान लीजिए कि हमारे पास S और T दो तार हैं जो छोटे अक्षरों से बने हैं। S में कोई भी अक्षर एक से अधिक बार नहीं आता है। S को पहले कुछ कस्टम क्रम में क्रमबद्ध किया गया था। हमें T के वर्णों को क्रमपरिवर्तन करना होगा ताकि वे उस क्रम से मेल खाएँ जो S को क्रमबद्ध किया गया था। अधिक विशेष रूप से, यदि x, S में y से पहले आता है, तो x लौटाए गए स्ट्रिंग में y से पहले होगा।
तो अगर S ="cba" और T ="abcd", तो आउटपुट "cbad" होगा। यहां "ए", "बी", "सी" एस में दिखाई देता है, इसलिए "ए", "बी", "सी" का क्रम "सी", "बी" और "ए" होना चाहिए। चूंकि "डी" एस में प्रकट नहीं होता है, यह टी में किसी भी स्थिति में हो सकता है। "डीसीबीए", "सीडीबीए", "सीबीडीए" भी मान्य आउटपुट हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट को खाली स्ट्रिंग के रूप में सेट करें
-
एक नक्शा m परिभाषित करें, और T में मौजूद प्रत्येक वर्ण की आवृत्ति को m में संग्रहीत करें
-
मैं के लिए 0 से लेकर S-1 के आकार के बीच
-
एक्स:=एस[i]
-
j के लिए 0 से m[x] - 1
. की सीमा में-
रिट:=रिट + एक्स
-
-
एम [एक्स] :=0
-
-
प्रत्येक जोड़ी के लिए इसे m -
. में-
यदि इसका मान> 0 है, तो
-
मैं के लिए 0 से इसके मान की सीमा में - 1
-
ret :=ret concatenate key of it
-
-
-
-
वापसी रिट
उदाहरण(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