 # COMPILER - Editorial

Author: Bruno Oliveira
Tester: Sergey Kulik
Editorialist: Lalit Kundu

EASY

### PROBLEM:

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:

1. S="" is regular.
2. S="<" + S1 + “>” is regular, if S1 is regular.
3. 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
``````

Complexity: O(N).

### AUTHOR’S AND TESTER’S SOLUTIONS:

7 Likes

Can anyone tell me why this code gives WA??

Try this case:

1

<<><>>

Output should be 6

1 Like

Thanks got it!!!  can i get sometest cases want to figure out where i am getting wrong, comipler of codeshef was flashing WRONG ANSWER

You assume, that max input length is 100, why?

See the second test case - http://ideone.com/Xxe1sf (answer is not 4 for sure)

1 Like

Can you help me where i m getting wrong
thank you so much

Can anyone tell me why my this Pascal code was giving wrong ans but same implementation in C++ passed ?

Can somebody please tell me the mistake that I did in this C code: http://ideone.com/HcmfNJ

Got a WA… :’(

for input

``````1
<<>
``````

your code returns 2, but correct is 0

Thanks a lot!

Can anyone post a java implementation for this?

Mine is here - http://www.codechef.com/viewsolution/3815607

combination of statements

``````char* a;
// ...
a[m][j]
``````

is strange isn’t it?

1 Like

Actually,
i used to work on Turbo c++ and it used to work on it.
and also i am new to codeshef.
But Yes It seems strange,
http://ideone.com/ObhNFA,
its working now but ,
time limit exceed,
but i m trying to develop better logic.

Incidentally a similar question was asked on forums a few month’s back.

Can anyone tell which case i am leaving ??
Have tried many times but cant get it Accepted.

Please give a test case where my code fails for compilers and parsers
[http://www.codechef.com/viewsolution/3876116] the above link is the code where i had written in java

You was kind of lucky, your code is not working on ideone I had to change

``````Scanner s = new Scanner(System.in);
String str = s.nextLine();
``````

to

``````//Scanner s = new Scanner(System.in);
String str = rea.nextLine();
``````

and the code returns 0 4 0 for input from problem statement http://ideone.com/UyDMNu , can you fork it and fix it on ideone?

//