संतुलित कोष्ठक अनुक्रम वाले जोड़ों की गणना करने का C++ प्रोग्राम

समस्या विवरण

हमें कोष्ठकों वाली स्ट्रिंग्स का एक ऐरे दिया गया है। लक्ष्य उन जोड़ों की गणना करना है जिन्हें मिलाकर एक संतुलित कोष्ठक अनुक्रम बनाया जा सके। कोष्ठक तब संतुलित होते हैं जब खोलने और बंद करने वाले कोष्ठकों की संख्या समान हो। एक बार उपयोग किया गया कोष्ठक दूसरी जोड़ी के लिए नहीं गिना जा सकता।

उदाहरण

इनपुट: {")()())", "(", ")(", ")(", ")"}

आउटपुट: 1

व्याख्या: वैध जोड़ी इंडेक्स (2,5) पर है।

इनपुट: {")()())", "((", "(", ")(", ")(", ")"}

आउटपुट: 2

व्याख्या: वैध जोड़ियाँ: (1,2) और (3,6)।

दृष्टिकोण

प्रत्येक स्ट्रिंग के लिए असंतुलित खोलने वाले (first) और बंद करने वाले (last) कोष्ठकों की गणना करें। दो मैप um_1 और um_2 का उपयोग करें:

• um_1: वे स्ट्रिंग्स जिनमें केवल अतिरिक्त खोलने वाले कोष्ठक हैं
• um_2: वे स्ट्रिंग्स जिनमें केवल अतिरिक्त बंद करने वाले कोष्ठक हैं
• पूरी तरह संतुलित स्ट्रिंग्स (first=0, last=0) स्वयं जोड़े बना सकती हैं

एल्गोरिदम

1. प्रत्येक स्ट्रिंग के लिए first (खोलने वाले) और last (बंद करने वाले) गिनें
2. यदि first==1 && last!=1 → um_1[first]++
3. यदि last==1 && first!=1 → um_2[last]++
4. यदि first==0 && last==0 → count++
5. count = count / 2 (संतुलित स्ट्रिंग्स आपस में जोड़ी बनाती हैं)
6. प्रत्येक कुंजी के लिए count += min(um_1[key], um_2[key])
7. गणना लौटाएँ

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

int parentheses(string paran[], int size) {
    int count = 0;
    unordered_map<int, int> um_1, um_2;
    
    for (int i = 0; i < size; i++) {
        string str = paran[i];
        int first = 0, last = 0;
        
        for (char c : str) {
            if (c == '(') first++;
            else {
                if (first > 0) first--;
                else last++;
            }
        }
        
        if (first > 0 && last == 0) um_1[first]++;
        else if (last > 0 && first == 0) um_2[last]++;
        else if (first == 0 && last == 0) count++;
    }
    
    count /= 2;
    for (auto& it : um_1) {
        count += min(it.second, um_2[it.first]);
    }
    return count;
}

int main() {
    string paran[] = {")()())", "(", ")(", ")(", ")"};
    int size = sizeof(paran) / sizeof(paran[0]);
    cout << "Count: " << parentheses(paran, size);
    return 0;
}

आउटपुट

Count: 1