Markup Depth Checker
Medium · stack
A tiny document language wraps text in tags. The string doc is made of plain text and tags, and a tag is one of:
- an opening tag,
<name> - a closing tag,
</name> - a self-closing tag,
<name/>
A name is 1 to 10 lower-case letters. Plain text never contains the characters < or >, so every < starts a tag and every tag ends at the next >.
A document is well formed when every opening tag is closed by a closing tag with the same name, and tags nest properly: a closing tag always closes the opening tag that was opened most recently and is still open. Self-closing tags open and close in one go, so they need no partner.
The depth of a document is the largest number of tags that are open at the same time, counting a self-closing tag as open while it is being read. Text outside any tag has depth 0.
Return the depth of the document if it is well formed, or -1 if it is not.
Examples
Example 1
Input: doc = "<p>Hello <b>world</b></p>"
Output: 2
The paragraph is open while the bold tag is open inside it, so two tags are open at the deepest point.
Example 2
Input: doc = "<ul><li>a</li><li>b<br/></li></ul>"
Output: 3
Inside the second list item the line break counts as a third open tag.
Example 3
Input: doc = "<a><b></a></b>"
Output: -1
The closing tag for a arrives while b is still the most recently opened tag, so the nesting is broken.
Constraints
- 1 <= len(doc) <= 10^5
- Every
<starts a tag of one of the three forms above, which ends at the next>. - Tag names are 1 to 10 lower-case letters; plain text may hold any other characters.