C++-এ Minimum Remove to Make Valid Parentheses

ধরি আমাদের একটি স্ট্রিং s আছে যা '(', ')' এবং लोয়ারকেস ইংলিশ ক্যারেক্টার দিয়ে গঠিত। আমাদের মিনিমাম সংখ্যক প্যারেনথেসিস ( '(' বা ')', যেকোনো পজিশনে ) রিমুভ করতে হবে যাতে ফলাফল প্যারেনথেসিস স্ট্রিংটি ভ্যালিড হয় এবং যেকোনো একটি ভ্যালিড স্ট্রিং রিটার্ন করতে হবে। একটি প্যারেনথেসিস স্ট্রিং ভ্যালিড হয় যখন নিচের সব ক্রাইটেরিয়া পূরণ হয়:

এটি একটি খালি স্ট্রিং, শুধু লোয়ারকেস ক্যারেক্টার ধারণ করে, অথবা
এটি AB ফর্মে লেখা যায় (A কনক্যাটেনেটেড উইথ B), যেখানে A এবং B ভ্যালিড স্ট্রিং, অথবা
এটি (A) ফর্মে লেখা যায়, যেখানে A একটি ভ্যালিড স্ট্রিং।

ইনপুট যদি "a)b(c)d" হয়, তবে আউটপুট হবে "ab(c)d"

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

একটি স্ট্যাক st ডিফাইন করুন
i = 0 থেকে s.size() - 1 পর্যন্ত লুপ চালান
- যদি s[i] = '(', তবে i স্টকে পাশ করুন
- অন্যথায় যখন s[i] = ')', তবে
  - যদি স্ট্যাক খালি না হয়, তবে স্ট্যাক থেকে পপ করুন, অন্যথায় s[i] = '*' সেট করুন
যখন পর্যন্ত st খালি নয়,
- s[st.top()] = '*' সেট করুন
- স্ট্যাক থেকে পপ করুন
ans := খালি স্ট্রিং
i = 0 থেকে s.size() - 1 পর্যন্ত লুপ চালান
- যদি s[i] '*' না হয়, তবে ans := ans + s[i]
ans রিটার্ন করুন

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য:

উদাহরণ

#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;
    }
};

int main() {
    Solution ob;
    cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}

ইনপুট

"a)b(c)d"

আউটপুট

ab(c)d