Given a bracket sequence, print the length of largest prefix that is a regular bracket sequence.
EXPLANATION:
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
Please give a test case where my code fails for compilers and parsers
[CodeChef: Practical coding for everyone] the above link is the code where i had written in java
Can someone provide a solution for the same above problem if the word prefix was removed. I am getting considerable difficulties in doing this version. Eg. for <<<<<<<<> output:2 , for <><><<<<<<<<<> output:4.
My problem is that how do we track whether the new contiguous sub sequence extends the previous one or not. As in <<>><<>> output:8 but for <<>><<<>> output:4.
Please help!
you can solve the problem using divide and conquer approach with a segment tree. At each node of the segment tree, store the following 5 variables:
l -> the maximum positive sum from right end
li -> the index at which the maximum sum is achieved
r -> the minimum negative sum from left end
ri -> the index at which this minimum sum is achieved
b -> longest perfect bracket sequence in the interval
So, for a node N, the best can be calculated as the maximum of b values of the children, or taking the joint of the r value of the right child and l value of the left child. if mod of l of left child is less than mod of r of right child, then just find the index in the right child where the prefix sum is equal to -l. similar procedure if mod of r is smaller than mod of l. this is work in NlogN.
