Not As Hard As It Seems

Sakib and Shamim are good friends. As Sakib is a little naughty, every night before exam he disturbs Shamim. One day Shamim got an idea to get rid of Sakib. Shamim gave him a sequence of parenthesis and bracket and told him to determine the maximum length of a valid sequence.


This is a companion discussion topic for the original entry at https://toph.co/p/not-as-hard-as-it-seems

I am not understanding why the output is 4. Can anyone explain me? @hjr265

2 Likes

Iam also having the same doubt

1 Like

@Aritra15 @mustafizz_22 Looks like the statement of this problem wasn’t very clear in its definition of what a valid subsequence is. I have tried to make some quick changes to it to make the statement clearer.

2 Likes

#include <bits/stdc++.h>

using namespace std;

int main() {stack s;
string a;

		while((cin>>a))
		{int max=0;
			int count=0;
		for(int i=0;i<a.size();i++)
		{char c=a[i];
		 if(i!=0 && s.empty()){if(count>max)max=count;
							   count=0;}
		 if(c=='{' || c=='[' || c=='(')s.push(c);
		 else if(c=='}' && s.top()=='{'){s.pop();
										 count++;}
		 else if (c==']' && s.top()=='['){s.pop();
										  count++;}

else if (c==’)’ && s.top()==’(’){s.pop();
count++;}
}
cout<<2*max<<endl;}

return 0;

}
Can anyone please help me to correct this code?I really can’t find my mistake.

#include <bits/stdc++.h>
#define optimize ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define ll long long
#define vi vector
#define pb push_back
#define lp(i,a,b) for(int i = a ; i <= b ; i ++)
#define rlp(i,a,b) for(int i = b ; i >= a ; i --)
#define a_sort(v) sort(v.begin(), v.end())
#define d_sort(v) sort(v.rbegin(), v.rend())
#define pii pair<int,int>
using namespace std ;

const int MOD = 1E9 + 7 ;
int main() {

#ifdef debug
freopen("input.txt", "r", stdin) ;
freopen("output.txt", "w", stdout) ;
#endif // debug

optimize
string s ;
while(cin >> s) {
    int l = s.size() ;
    if(l == 1) cout << 1 << endl ;
    else {
        int mx = 0 , cnt = 0 ; stack<char> st ;
        lp(i, 0, l-1) {
            char current = s[i] ; // cout << "current = " << current << endl ;
            if(st.empty()) {
                st.push(current) ; // cout << "stack empty, " << st.top() << " was pushed" << endl ;
                cnt = 0 ;
            }
            else {
                char top = st.top() ; // cout << "stack top = " << top << endl ;
                if(current == ']') {
                    if(top == '[') {
                        st.pop() ; // cout << "[ was poped" << endl ;
                        cnt += 2 ;
                        mx = max(cnt, mx) ;
                    }
                    else {
                        st.push(current) ;
                        // cout << "] was pushed" << endl ;
                    }
                }
                else if(current == ')') {
                    if(top == '(') {
                        st.pop() ; // cout << "( was poped" << endl ;
                        cnt += 2 ;
                        mx = max(cnt, mx) ;
                    }
                    else {
                        st.push(current) ;
                        // cout << ") was pushed" << endl ;
                    }
                }
                else st.push(current) ; // cout << current << " was pushed" << endl ;
            }
            // cout << "mx = " << mx << " cnt = " << cnt << endl ;
        }
    cout << mx << endl ;
    }
}

}

what’s wrong with this code?

What should be the answer for these inputs ?
[()()]
2 , 4 or 6

[()(]]
2 or 4

Please reply soon.
I’m confused. I tried 4 times, but wrong answer in test 2. :’(