C++ এ বৈধ বন্ধনী তৈরি করতে ন্যূনতম সরান

ধরুন আমাদের '(' , ')' এবং ছোট হাতের ইংরেজি অক্ষরের একটি স্ট্রিং আছে। আমাদের ন্যূনতম সংখ্যক বন্ধনী ('(' বা ')', যেকোনো অবস্থানে ) অপসারণ করতে হবে যাতে ফলস্বরূপ বন্ধনী স্ট্রিং বৈধ হয় এবং কোনো বৈধ স্ট্রিং ফেরত দেয়। একটি বন্ধনী স্ট্রিং বৈধ যখন এই সমস্ত মানদণ্ড পূরণ হয় −

• এটি খালি স্ট্রিং, শুধুমাত্র ছোট হাতের অক্ষর ধারণ করে, অথবা

• এটি AB এর ফর্ম হিসাবে লেখা যেতে পারে (B এর সাথে A সংযুক্ত), যেখানে A এবং B বৈধ স্ট্রিং, অথবা

• এটি (A) এর ফর্ম হিসাবে লেখা যেতে পারে, যেখানে A একটি বৈধ স্ট্রিং।

সুতরাং ইনপুট যদি “a)b(c)d” এর মত হয়, তাহলে আউটপুট হবে “ab(c)d”

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

• একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন

• i এর জন্য 0 থেকে s আকারের সীমার মধ্যে

  • যদি s[i] ='(', তাহলে i ঢোকান st

    এ

  • অন্যথায় যখন s[i] হয় ‘)’, তখন

    • যদি স্ট্যাক খালি না হয়, তাহলে স্ট্যাক থেকে পপ করুন, অন্যথায় s[i] =‘*’

• যখন সেন্ট খালি নয়,

  • s[স্ট্যাকের শীর্ষ উপাদান] ='*'

  • স্ট্যাক থেকে পপ

• উত্তর :=খালি স্ট্রিং

• 0 থেকে s - 1

  এর আকারের মধ্যে i এর জন্য

  • যদি s[i] '*' না হয়, তাহলে উত্তর :=ans + s[i]

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string minRemoveToMakeValid(string s) {
      stack <int> st;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '(')st.push(i);
         else if(s[i] == ')'){
            if(!st.empty())st.pop();
            else s[i] = '*';
         }
      }
      while(!st.empty()){
         s[st.top()] = '*';
         st.pop();
      }
      string ans = "";
     for(int i = 0; i < s.size(); i++){
        if(s[i] != '*')ans += s[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}

ইনপুট

"a)b(c)d"

আউটপুট

ab(c)d