सी++ में दो स्ट्रिंग एनाग्राम बनाने के लिए न्यूनतम चरणों की संख्या

मान लीजिए कि हमारे पास दो समान आकार के तार s और t हैं। एक चरण में हम t के किसी भी वर्ण को चुन सकते हैं और इसे किसी अन्य वर्ण से बदल सकते हैं। हमें t को s का विपर्यय बनाने के लिए आवश्यक न्यूनतम चरणों की संख्या ज्ञात करनी होगी। नोट:एक स्ट्रिंग का विपर्यय एक स्ट्रिंग है जिसमें भिन्न (या समान) क्रम वाले समान वर्ण होते हैं।

इसलिए यदि इनपुट "yxy" और "xyx" जैसा है, तो आउटपुट 1 होगा, क्योंकि केवल एक वर्ण को बदलने की आवश्यकता है।

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

• n :=अक्षरों का आकार s

• एक नक्शा m बनाएं, और इसे s में मौजूद प्रत्येक वर्ण की आवृत्ति के साथ भरें, दूसरा नक्शा m2 बनाएं, और इसे t में मौजूद प्रत्येक वर्ण की आवृत्ति से भरें

• रिट :=n

• प्रत्येक की-वैल्यू पेयर के लिए इसे m

  . में जोड़ें

  • x :=इसका न्यूनतम मान, और m2 का मान [इसका मान]

  • रिट को 1 से घटाएं

• वापसी रिट

उदाहरण (C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minSteps(string s, string t) {
      int n = s.size();
      map <char, int> m1;
      for(int i = 0; i < s.size(); i++){
         m1[s[i]]++;
      }
      int ret = n;
      map <char, int> m2;
      for(int i = 0; i < t.size(); i++){
         m2[t[i]]++;
      }
      map <char, int> :: iterator it = m1.begin();
      while(it != m1.end()){
         //cout << it->first << " " << it->second << " " << m2[it->first] << endl;
         int x = min(it->second, m2[it->first]);
         ret -= x;
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.minSteps("yxy", "xyx"));
}

इनपुट

"yxy"
"xyx"

आउटपुट

1