C++ में न्यूनतम ब्रैकेट जोड़

मान लीजिए कि हमारे पास एक स्ट्रिंग है जिसमें केवल '(' और ')' है, हमें स्ट्रिंग को संतुलित करने के लिए सम्मिलित किए जा सकने वाले कोष्ठकों की न्यूनतम संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट "(())) (" जैसा है, तो आउटपुट 2 होगा "(()))(", इसे संतुलित किया जा सकता है जैसे"((()))()"।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• :=0, सीएनटी:=0

• इनिशियलाइज़ i:=0 के लिए, जब i <साइज़ ऑफ़ s, अपडेट (i से 1 तक बढ़ाएँ), करें -

  • अगर s[i] '(' के समान है, तो -

    • (1 से बढ़ाएँ)

  • अन्यथा

    • यदि o शून्येतर है, तो -

      • (o 1 से घटाएं)

    • अन्यथा

      • (cnt 1 से बढ़ाएँ)

• वापसी सीएनटी + ओ

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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