मान लीजिए हमारे पास S और T दो स्ट्रिंग्स हैं जो लोअरकेस अक्षरों से बनी हैं। S में, कोई अक्षर एक से अधिक बार नहीं आता। S को पहले किसी कस्टम ऑर्डर में सॉर्ट किया गया था। हमें T के वर्णों को क्रमबद्ध करना है ताकि वे उस क्रम से मेल खाएं जिसमें S को सॉर्ट किया गया था। अधिक विशेष रूप से, यदि x, S में y से पहले आता है, तो x, लौटाई गई स्ट्रिंग में y से पहले आएगा।
उदाहरण के लिए, यदि 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में प्रत्येक जोड़ीitके लिए- यदि
it का मान > 0, तोiको 0 सेit के मान - 1तक लूप करेंret := ret को it की कुंजी के साथ संयोजित करें
- यदि
retलौटाएं
उदाहरण (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