C++-এ সমতুল্য খোলা ও বন্ধ ব্র্যাকেট বিশিষ্ট জোড়া সংখ্যা গণনা

আমাদের একটি স্ট্রিং অ্যারে দেওয়া আছে যেটিতে বন্ধনী (parentheses) রয়েছে। লক্ষ্য হল এমন জোড়া সিকোয়েন্স বের করা যাতে তাদের মিলিয়ে একটি সমতুল্য (balanced) বন্ধনী সিকোয়েন্স তৈরি হয়। সমতুল্য বন্ধনী বলতে খোলা এবং বন্ধ ব্র্যাকেটের সংখ্যা সমান থাকাকে বোঝায়। একবার ব্যবহৃত বন্ধনী দ্বিতীয়বারের জন্য ব্যবহার করা যাবে না।

উদাহরণ

ইনপুট: paran[] = {")()())", "(", ")(", ")(", ")"}

আউটপুট: ১

ব্যাখ্যা: প্রথম এলিমেন্ট ")()())"-এ ৪টি বন্ধ এবং ২টি খোলা ব্র্যাকেট আছে। এর সাথে জোড়া বানাতে ২টি খোলা ব্র্যাকেট দরকার যা অন্য কোনো এলিমেন্টে নেই। ভ্যালিড জোড়া পাওয়া যায় (২, ৫) ইনডেক্সে।

ইনপুট: paran[] = {")()())", "((", "(", ")(", ")(", ")"}

আউটপুট: ২

ব্যাখ্যা: ভ্যালিড জোড়া: (১, ২) এবং (৩, ৬)।

অ্যালগরিদম

প্রতিটি স্ট্রিং এর জন্য খোলা (first) এবং বন্ধ (last) ব্র্যাকেটের অতিরিক্ত সংখ্যা গণনা করুন।
যদি কোনো স্ট্রিং নিজে সমতুল্য হয় (first=0, last=0) তবে সেটি নিজে নিজের সাথে জোড়া বানাতে পারে। এগুলো দিয়ে count/2 জোড়া তৈরি হবে।
যেসব স্ট্রিং-এ শুধু অতিরিক্ত খোলা ব্র্যাকেট আছে (first>0, last=0) সেগুলো um_1 ম্যাপে রাখুন।
যেসব স্ট্রিং-এ শুধু অতিরিক্ত বন্ধ ব্র্যাকেট আছে (first=0, last>0) সেগুলো um_2 ম্যাপে রাখুন।
um_1 এবং um_2-র মিল থাকলে min(um_1[val], um_2[val]) দিয়ে কাউন্ট বাড়ান।

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 len = str.length();
        int first = 0, last = 0;
        
        for (int j = 0; j < len; j++) {
            if (str[j] == '(') 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 of pairs of parentheses sequences such that parentheses are balanced are: " 
         << parentheses(paran, size);
    return 0;
}

আউটপুট

Count of pairs of parentheses sequences such that parentheses are balanced are: 1