मान लीजिए हमें एक स्ट्रिंग s दी गई है, और इंडेक्स के जोड़ों का एक ऐरे pairs जहां pairs[i] = [a, b] स्ट्रिंग के 2 इंडेक्स (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 से भरें
साइज n का एक स्ट्रिंग ret बनाएं और इसे * से भरें
i को 0 से pairs के साइज तक लूप करें:
u := pairs[i][0] और v := pairs[i][1]
अगर u का पैरेंट v के पैरेंट के बराबर है, तो अगले इटरेशन पर जाएं
parent[u का पैरेंट] := v का पैरेंट
साइज n का एक ऐरे arr1 डिफाइन करें
i को 0 से n-1 तक लूप करें: s[i] को arr[parent of i] में इंसर्ट करें
i को 0 से n-1 तक लूप करें: arr[i] को राइट से पढ़कर सॉर्ट करें
i को 0 से 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"