A monitoring dashboard logs a stream of labeled tag events. Each event is one token: either an opening tag <name> or a closing tag </name>, where name is 1-10 lowercase English letters. Tags must nest correctly, like in XML/HTML: the most recently opened tag must be the next one closed.
Scan the tokens left to right (1-indexed) and find the first token that breaks correct nesting. A token breaks nesting if it is a closing tag </name> and either no tag is currently open, or the most recently opened (and not yet closed) tag has a different name.
If every closing tag matches correctly but some opened tag is never closed by the end of the stream, the stream is still invalid — in that case report the position of the earliest still-open tag (the first tag ever opened that never got closed).
If neither situation occurs, the stream is fully valid.
Line 1: an integer n, the number of tokens.
Line 2: n space-separated tokens, each of the form <name> or </name>.
Print VALID if the whole stream is correctly nested. Otherwise print a single integer: the 1-indexed position described above.
name consists of 1 to 10 lowercase English letters.Example 1
Input
4 <a> <b> </b> </a>
Expected
VALID
Explanation
b is opened after a, then closed before a, so the nesting is correct throughout: VALID.
Example 2
Input
2 <a> </b>
Expected
2
Explanation
Token 2 tries to close b, but the only open tag is a, so token 2 (1-indexed) is the first violation.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →