Header Ad

HackerEarth Bracket sequences problem solution

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


Post a Comment

2 Comments

  1. it would be very helpful if you right some logic for the for loop
    what 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++;
    }

    ReplyDelete
  2. 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??

    like for
    1) s = ")()()(" here valid sequence exist and the valid sequence is ()()()
    2) s = "(()))" here valid sequence does not exist

    ReplyDelete