Given a bracket sequence, print the length of largest prefix that is a regular bracket sequence.
A regular bracket sequence is defined as follows:
- S="" is regular.
- S="<" + S1 + “>” is regular, if S1 is regular.
- S=S1 concat S2 is regular, if S1 and S2 are regular.
If S is regular bracket sequence, for any i, number of closing brackets in S[0,i] should not exceed number of opening brackets. Also, if number of opening brackets is equal to number of closing brackets in S[0,i], S[0,i] is a regular bracket sequence.
def check(s): t=0,ans=0 for i=0 to N-1: if s[i]=='<': t++; else: t--; //Now, if t=0, means, the string s[0,i] is valid. if t==0: ans=max(ans,i+1) else if t<0: break //string s whole is invalid. print ans