सी++ में स्ट्रिंग्स को समान बनाने के लिए न्यूनतम स्वैप

मान लीजिए कि हमारे पास समान लंबाई के दो तार s1 और s2 हैं जिनमें केवल "x" और "y" अक्षर हैं। हमारा काम इन दोनों तारों को एक दूसरे के बराबर बनाना है। हम अलग-अलग स्ट्रिंग्स से संबंधित किन्हीं दो वर्णों को स्वैप कर सकते हैं, जिसका अर्थ है - स्वैप s1[i] और s2[j]। हमें s1 और s2 को समान बनाने के लिए आवश्यक न्यूनतम संख्या में स्वैप का पता लगाना होगा, या यदि ऐसा करना असंभव है तो -1 लौटाएं। इसलिए यदि स्ट्रिंग्स s1 ="xy" और s2 ="yx" हैं, तो आउटपुट 2 होगा। यदि हम s1[0] और s2[0], s1 ="yy", s2 ="xx" को स्वैप करते हैं। फिर s1[0] और s2[1], s1 ="xy", s2 ="xy" को स्वैप करें।

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

• X1, x2, y1 और y2 को 0 के रूप में सेट करें
• i के लिए 0 से s1 के आकार के बीच
  • a :=s1[i] और b :=s2[i]
  • यदि a, b के समान नहीं है, तो
    • यदि a ='x' है तो x1 बढ़ाएँ, अन्यथा y1 को 1 से बढ़ाएँ
    • यदि b ='x' है तो x2 बढ़ाएँ, अन्यथा y2 को 1 से बढ़ाएँ
• यदि (x1 + x2) विषम है या (y1 + y2) विषम है, तो -1 लौटाएं
• रिटर्न x1/2 + y1/2 + (X1 mod 2) * 2

उदाहरण(C++)

एक बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumSwap(string s1, string s2) {
      int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
      for(int i = 0; i < s1.size(); i++){
         char a = s1[i];
         char b = s2[i];
         if(a != b){
            if(a == 'x')x1++;
            else y1++;
            if(b == 'x')x2++;
            else y2++;
         }
      }
      if ((x1 + x2) & 1 || (y1 + y2) & 1)return -1;
      return x1/2 + y1/2 + (x1 % 2) * 2;
   }
};
main(){
   Solution ob;
   cout <<ob.minimumSwap("xy", "yx");
}

इनपुट

"xy"
"yx"

आउटपुट

2