Tag Validator — Stack-Based XML Parsing (LeetCode 591)

Tag Validator (LeetCode 591) asks you to validate whether a string represents valid XML-like code. This is a hard problem that tests your ability to carefully parse structured text using a stack — the same concept behind real XML parsers and compilers.

The Problem

A valid string must satisfy these rules:

1. Closed tags: Every <TAG_NAME> must have a matching </TAG_NAME>
2. Tag names: 1-9 uppercase English letters only
3. Content: Everything between matching tags is valid content (including other tags)
4. CDATA: <![CDATA[content]]> sections can contain anything, including unmatched tags
5. Wrapping: The entire string must be wrapped in a single valid tag

Valid:   "<DIV>content</DIV>"
Valid:   "<DIV><P>text</P></DIV>"
Valid:   "<DIV><![CDATA[<br>]]></DIV>"
Invalid: "<DIV>"                    (no closing tag)
Invalid: "<div></div>"             (lowercase)
Invalid: "<TOOLONGTAGNAME></TOOLONGTAGNAME>"  (>9 chars)

Approach: Stack + Careful Parsing

We iterate through the string character by character, using a stack to track open tags:

1. When we see <![CDATA[, skip until we find ]]>
2. When we see </, extract the tag name and match against the stack top
3. When we see <, extract the tag name and push onto the stack
4. Track whether we have ever had a valid wrapping tag

def isValid(code: str) -> bool:
    """
    Validate XML-like code using a stack.
    Time: O(n), Space: O(n) for the stack
    """
    stack = []
    i = 0
    n = len(code)

    # The entire code must be wrapped in a valid tag
    if not code.startswith("<"):
        return False

    while i < n:
        # We finished processing but stack had tags that closed
        # and there is remaining content outside
        if not stack and i > 0:
            return False

        # Check for CDATA
        if code[i:i+9] == "<![CDATA[":
            # CDATA only valid inside a tag
            if not stack:
                return False
            j = code.find("]]>", i + 9)
            if j == -1:
                return False
            i = j + 3

        # Check for closing tag
        elif code[i:i+2] == "</":
            j = code.find(">", i + 2)
            if j == -1:
                return False
            tag_name = code[i+2:j]
            if not is_valid_tag(tag_name):
                return False
            if not stack or stack[-1] != tag_name:
                return False
            stack.pop()
            i = j + 1

        # Check for opening tag
        elif code[i] == "<":
            j = code.find(">", i + 1)
            if j == -1:
                return False
            tag_name = code[i+1:j]
            if not is_valid_tag(tag_name):
                return False
            stack.append(tag_name)
            i = j + 1

        else:
            # Regular content character
            i += 1

    return len(stack) == 0


def is_valid_tag(tag: str) -> bool:
    """Check if tag name is 1-9 uppercase letters."""
    if not tag or len(tag) > 9:
        return False
    return all(c.isupper() for c in tag)

Step-by-Step Trace

Input: "<DIV><P>hello</P><![CDATA[<br>]]></DIV>"

i=0:  "<DIV>"  → open tag "DIV" → push → stack = ["DIV"]
i=5:  "<P>"    → open tag "P"   → push → stack = ["DIV", "P"]
i=8:  "hello"  → content, skip to next '<'
i=13: "</P>"   → close tag "P"  → matches stack top → pop → stack = ["DIV"]
i=17: "<![CDATA[<br>]]>" → CDATA section, skip to after "]]>"
i=33: "</DIV>" → close tag "DIV" → matches stack top → pop → stack = []
i=39: end of string, stack empty → VALID

Tricky Edge Cases

# Empty tag name
assert isValid("<></>") == False

# Tag name too long (>9 chars)
assert isValid("<ABCDEFGHIJ></ABCDEFGHIJ>") == False

# Lowercase tags
assert isValid("<div></div>") == False

# Content outside root tag
assert isValid("<A></A>extra") == False

# CDATA outside any tag
assert isValid("<![CDATA[content]]>") == False

# Nested CDATA-like text inside CDATA (only first ]]> matters)
assert isValid("<A><![CDATA[]]>]]></A>") == False
# Because ]]> at position 15 closes the CDATA, leaving "]]></A>"
# which means "]]>" is content, then </A> closes properly

# Multiple root tags
assert isValid("<A></A><B></B>") == False

# Properly nested
assert isValid("<A><B><C></C></B></A>") == True

Why the “Stack Empty But Not Done” Check Matters

# Without the check: "<A></A><B></B>" would be accepted
# The check "if not stack and i > 0: return False" ensures
# that once the root tag closes, no more content follows.

This is critical: XML requires a single root element. After the root closes, nothing else should remain.

The Parsing State Machine

The parser essentially has three modes:

State	Trigger	Action
Normal	Regular character	Skip (content)
Open tag	< followed by uppercase	Push tag name
Close tag	</	Pop and match
CDATA	<![CDATA[	Skip until ]]>

Complexity Analysis

Metric	Value
Time	O(n) — single pass through the string
Space	O(n) — stack depth equals nesting depth

The find() calls do not add extra complexity because they advance i to the found position, so each character is processed at most twice.

When to Use This Pattern

Use stack-based tag matching when:

• Parsing nested or balanced structures (HTML, XML, JSON brackets)
• The problem involves matching open/close delimiters with rules
• You need to handle escape sequences or special blocks (like CDATA)
• Building a tokenizer or parser for structured text

This exact pattern powers real-world XML validators, HTML sanitizers, and bracket-matching in IDEs.

Common Mistakes

1. Not validating tag names — must be 1-9 uppercase letters only
2. Allowing content outside root tag — the entire string must be inside one tag pair
3. Not handling CDATA correctly — must find the matching ]]>, not parse inside
4. Off-by-one errors when extracting substrings between < and >
5. Forgetting that CDATA must be inside a tag — cannot appear at the top level

Related Problems

Problem	Key Difference
Valid Parentheses (LC 20)	Simpler — just brackets, no names
Exclusive Time of Functions (LC 636)	Stack for function call parsing
Basic Calculator (LC 224)	Stack for expression parsing
HTML Entity Parser (LC 1410)	String replacement, not validation
Decode String (LC 394)	Stack for nested encoded strings

Key Takeaways

• Tag validation is a parsing problem perfectly suited for a stack
• The stack tracks open tags; closing tags must match in LIFO order
• CDATA sections are opaque blocks — skip everything inside them
• Always validate tag names and enforce single-root-element rules
• This pattern directly transfers to building real parsers and compilers