Remove Balance Solution || Codechef Starters - 37

-

        

Remove Balance Solution 

Codechef Starters - 37
Problem Code : REMBAL

Solution :

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
    ll t = 1;
    cin >> t;
    while (t--)
    {
        string s;
        cin >> s;
        ll n = s.size();
        stack<ll> st;
        for (ll i = 0; i < n; i++)
        {
            if (st.empty())
            {
                st.push(i);
            }
            else if (s[st.top()] == '(' && s[i] == ')')
            {
                st.pop();
            }
            else
            {
                st.push(i);
            }
        }
        vector<ll> v;
        while (!st.empty())
        {
            ll k = st.top();
            v.push_back(k);
            st.pop();
        }
        ll k = v.size();
        ll ans = 0;
        if (k != 0)
        {
            if (v[0] == n - 1)
            {
                ans = 0;
                for (ll i = 0; i < k - 1; i++)
                {
                    if (v[i] - v[i + 1] > 1)
                    {
                        ans++;
                    }
                }
                if (v[k - 1] > 0)
                {
                    ans++;
                }
            }
            else
            {
                ans++;
                for (ll i = 0; i < k - 1; i++)
                {
                    if (v[i] - v[i + 1] > 1)
                    {
                        ans++;
                    }
                }
                if (v[k - 1] > 0)
                {
                    ans++;
                }
            }
        }
        else
        {
            ans = 1;
        }
        cout << k << " " << ans << "\n";
    }
}

Comments

Post a Comment