In this HackerEarth Bracket sequences problem solution A bracket sequence is a string that contains only characters '(' and ')'.

A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences '()()' and '(())' are correct. The resulting expressions of these sequences are: '(1)+(1)' and '((1+1)+1)'. However, '(', ')(', and '(' are incorrect bracket sequences. 

You are given a bracket sequence s(s1 s2...sn), where si denotes the type of 's bracket (open or close). It is not mandatory that s is necessarily correct. Your task is to determine the number of i's such that sisi+1...sns1s2...si-1 is a correct bracket sequence.


HackerEarth Bracket sequences problem solution


HackerEarth Bracket sequences problem solution.

#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)1e6 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 
const double pi = acos(-1.0);

#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        

char s[maxn];
int n, cnt, bal, mn = inf;
void solve(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    forn(i, 1, n){
        if(s[i] == '(') bal++;
        else bal--;
        if(mn > bal) mn = bal, cnt = 0;
        if(mn == bal) cnt++;
    }
    if(bal){
        puts("0");
        return;
    }
    printf("%d", cnt);
}

main () {
    int t = 1;
    while(t--)
        solve(); 
}       

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn = 3e2 + 14;
string s;
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> s;
    map<int, int> mp;
    int su = 0;
    for(auto c : s){
        su += (c == '(' ? +1 : -1);
        mp[su]++;
    }
    cout << (su == 0) * mp.begin() -> second << '\n';
}