C++-এ স্ট্রিং ব্যালেন্স করার জন্য ন্যূনতম ব্র্যাকেট যোগ করার প্রোগ্রাম

সমস্যা বিবরণ

শুধু '(' এবং ')' ধারণকারী একটি স্ট্রিং দেওয়া থাকলে, সেটি ব্যালেন্সড করার জন্য ন্যূনতম কতগুলো ব্র্যাকেট যোগ করতে হবে তা বের করুন।

উদাহরণ: "(()))(" → ২টি ব্র্যাকেট যোগ করলে "((()))()" হয়।

সমাধানের পদ্ধতি

1. o = 0 (ওপেন ব্র্যাকেট কাউন্ট), cnt = 0 (প্রয়োজনীয় ক্লোজ ব্র্যাকেট)।
2. স্ট্রিং ট্রাভার্স করুন:
   • '(' হলে: o++
   • ')' হলে:
     • o > 0 হলে: o-- (ম্যাচ করা)
     • অন্যথায়: cnt++ (এক্সট্রা ক্লোজ ব্র্যাকেট)৷
3. উত্তর = cnt + o (বাকি ওপেন + প্রয়োজনীয় ক্লোজ)۔

C++ কোড উদাহরণ

#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("(()))(");
    return 0;
}

আউটপুট

2

জটিলতা

• সময়: O(n)
• স্থান: O(1)