सी ++ में स्वैप के साथ सबसे छोटा स्ट्रिंग

मान लीजिए कि हमने एक स्ट्रिंग s, और स्ट्रिंग जोड़े में सूचकांकों के जोड़े की एक सरणी दी है, जहां जोड़े [i] =[a, b] स्ट्रिंग के 2 सूचकांकों (0-अनुक्रमित) को इंगित करता है। हम दिए गए जोड़े में सूचकांक के किसी भी जोड़े में वर्णों को जितनी बार चाहें स्वैप कर सकते हैं। हमें लेक्सिकोग्राफिक रूप से सबसे छोटी स्ट्रिंग ढूंढनी है जिसे स्वैप का उपयोग करने के बाद बदला जा सकता है। इसलिए यदि इनपुट s ="dcab" और जोड़े =[[0,3], [1,2]] जैसा है, तो आउटपुट "bacd" होगा। एक्सचेंज एस [0] और एस [3], एस ="बीसीएडी", फिर एक्सचेंज एस [1] और एस [2], एस ="बैकड"।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n:=सरणी का आकार, पैरेंट:=आकार n की एक सरणी बनाएं, और इसे -1 से भरें

• n आकार की रिट नामक एक स्ट्रिंग बनाएं और इसे *

  . से भरें

• मेरे लिए 0 से लेकर जोड़े के आकार तक

  • यू:=जोड़े[i, 0] और वी:=जोड़े[i, 1]

  • यदि u का जनक v के जनक के समान है, तो अगले पुनरावृत्ति पर जाएं

  • माता-पिता [आप के माता-पिता]:=वी के माता-पिता

• n आकार की arr1 सरणी परिभाषित करें

• मैं के लिए 0 से n - 1 की सीमा में:s[i] को arr[i के माता-पिता] में सम्मिलित करें

• मैं के लिए 0 से n - 1 की सीमा में:दायीं ओर से मान पढ़कर गिरफ्तारी [i] को क्रमबद्ध करें

• मैं के लिए 0 से n - 1 की सीमा में -

  • ret[i] :=arr1 की अंतिम प्रविष्टि [i के माता-पिता]

  • arr1[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"