C++ এ ন্যূনতম বন্ধনী সংযোজন

ধরুন আমাদের একটি স্ট্রিং আছে যার মধ্যে শুধুমাত্র '(' এবং ')' আছে, আমাদের ন্যূনতম সংখ্যক বন্ধনী খুঁজে বের করতে হবে যা স্ট্রিংটিকে ভারসাম্যপূর্ণ করতে সন্নিবেশ করা যেতে পারে।

সুতরাং, যদি ইনপুট "(()))(" এর মত হয়, তাহলে আউটপুট হবে 2 হিসাবে "(()))(", এটিকে "((()))()" এর মত ভারসাম্যপূর্ণ করা যেতে পারে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• :=0, cnt :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি s[i] '(' এর মত হয়, তাহলে −

    • (o 1 দ্বারা বৃদ্ধি করুন)

  • অন্যথায়

    • o যদি অ-শূন্য হয়, তাহলে −

      • (o 1 দ্বারা হ্রাস করুন)

    • অন্যথায়

      • (1 দ্বারা cnt বাড়ান)

• cnt + o

  ফেরত দিন

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(string s) {
      int o = 0;
      int cnt = 0;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '('){
            o++;
         } else {
            if(o)
               o--;
            else
               cnt++;
         }
      }
      return cnt + o;
   }
};
int main(){
   Solution ob;
   cout << (ob.solve("(()))("));
}

Input:
"(()))("

2