मान लीजिए हमारे पास समान साइज के दो स्ट्रिंग्स s और t हैं। एक स्टेप में हम t के किसी भी कैरेक्टर को चुनकर उसे दूसरे कैरेक्टर से रिप्लेस कर सकते हैं। हमें t को s का एनाग्राम बनाने के लिए आवश्यक न्यूनतम स्टेप्स ढूंढने हैं। नोट: एक स्ट्रिंग का एनाग्राम एक ऐसी स्ट्रिंग है जिसमें समान कैरेक्टर्स होते हैं लेकिन अलग (या समान) क्रम में।
उदाहरण के लिए, अगर इनपुट "yxy" और "xyx" है, तो आउटपुट 1 होगा, क्योंकि केवल एक कैरेक्टर को रिप्लेस करने की आवश्यकता है।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
n := s में कैरेक्टर्स का साइज
एक मैप m बनाएं, और इसे s में मौजूद प्रत्येक कैरेक्टर की फ्रीक्वेंसी से भरें, एक और मैप m2 बनाएं, और इसे t में मौजूद प्रत्येक कैरेक्टर की फ्रीक्वेंसी से भरें
ret := n
m में प्रत्येक की-वैल्यू पेयर it के लिए:
x := it के वैल्यू और m2[it की वैल्यू] का मिनिमम
ret को x से घटाएं
ret लौटाएं
उदाहरण (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()){
int x = min(it->second, m2[it->first]);
ret -= x;
it++;
}
return ret;
}
};
int main(){
Solution ob;
cout << (ob.minSteps("yxy", "xyx"));
}
इनपुट
"yxy" "xyx"
आउटपुट
1