Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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


मान लीजिए हमारे पास समान साइज के दो स्ट्रिंग्स 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

  1. - C++ में न्यूनतम पृष्ठों का आवंटन

    न्यूनतम पृष्ठों का आवंटन एक प्रोग्रामिंग समस्या है। आइए इस समस्या पर विस्तार से चर्चा करते हैं और देखते हैं कि इसका समाधान क्या हो सकता है। कथन आपको n विभिन्न पुस्तकों के पृष्ठों की संख्या दी गई है। साथ ही, m छात्र हैं जिन्हें पुस्तकें आवंटित की जानी हैं। पुस्तकें पृष्ठों की संख्या के आरोही क्रम में

  1. - C++ में को-प्राइम ऐरे बनाने के लिए न्यूनतम इंसर्शन

    इस सेक्शन में हम एक और दिलचस्प समस्या देखेंगे। मान लीजिए हमारे पास N एलिमेंट्स का एक ऐरे है। हमें इस ऐरे को को-प्राइम ऐरे बनाने के लिए न्यूनतम इंटरसेक्शन पॉइंट्स ढूंढने हैं। को-प्राइम ऐरे में हर दो लगातार एलिमेंट्स का gcd 1 होता है। हमें ऐरे भी प्रिंट करना है।मान लीजिए हमारे पास {5, 10, 20} जैसे एलि

  1. - C++ प्रोग्राम ग्राफ को डिस्कनेक्ट करने के लिए काटने के लिए न्यूनतम एजेस की संख्या खोजने के लिए

    इस प्रोग्राम में हमें एक ग्राफ की एज कनेक्टिविटी ढूंढनी है। एक ग्राफ की एज कनेक्टिविटी का अर्थ है यह एक ब्रिज है, इसे हटाने पर ग्राफ डिस्कनेक्ट हो जाएगा। एक डिस्कनेक्टेड अनडायरेक्टेड ग्राफ में ब्रिज को हटाने पर कनेक्टेड कंपोनेंट्स की संख्या बढ़ जाती है। फंक्शन्स और सूडोकोड connections() एक रिकर्सि