मान लीजिए हमारे पास समान लंबाई के दो स्ट्रिंग्स s1 और s2 हैं जिनमें केवल "x" और "y" अक्षर हैं। हमारा कार्य इन दो स्ट्रिंग्स को एक-दूसरे के बराबर बनाना है। हम किन्हीं दो वर्णों को स्वैप कर सकते हैं जो अलग-अलग स्ट्रिंग्स से संबंधित हैं, जिसका अर्थ है - swap 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
