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.

`#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';

}

## 2 Comments

it would be very helpful if you right some logic for the for loop

ReplyDeletewhat exactly you are doing here??

forn(i, 1, n){

if(s[i] == '(') bal++;

else bal--;

if(mn > bal) mn = bal, cnt = 0;

if(mn == bal) cnt++;

}

please help me, how should i know for a given bracket sequence there exist a valid sequence and how would i found that valid sequence??

ReplyDeletelike for

1) s = ")()()(" here valid sequence exist and the valid sequence is ()()()

2) s = "(()))" here valid sequence does not exist