### PROBLEM LINK:

**Author:** Bruno Oliveira

**Tester:** Sergey Kulik

**Editorialist:** Lalit Kundu

### DIFFICULTY:

EASY

### PREREQUISITES:

AD-HOC

### 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:

- 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*=='<': 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).