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