Tag Validator - Practice Coding Problems

Tag Validator - Problem

String Stack Hard

Given a string representing a code snippet, implement a tag validator to parse the code and return whether it is valid.

A code snippet is valid if all the following rules hold:

The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.
A closed tag (not necessarily valid) has exactly the following format: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Among them, <TAG_NAME> is the start tag, and </TAG_NAME> is the end tag. The TAG_NAME in start and end tags should be the same.
A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid.
A valid TAG_NAME only contains upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid.
A valid TAG_CONTENT may contain other valid closed tags, cdata and any characters EXCEPT unmatched <, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME.
A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.
A < is unmatched if you cannot find a subsequent >. And when you find a < or </, all the subsequent characters until the next > should be parsed as TAG_NAME.
The cdata has the following format: <![CDATA[CDATA_CONTENT]]>. The range of CDATA_CONTENT is defined as the characters between <![CDATA[ and the first subsequent ]]>. CDATA_CONTENT may contain any characters. The function of cdata is to forbid the validator to parse CDATA_CONTENT.

Input & Output

Example 1 — Valid Simple Tag

$ Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"

› Output: true

💡 Note: The code is wrapped in a valid closed tag

. The tag name DIV is valid (uppercase, length 3). The content contains CDATA which is properly formatted.

Example 2 — Invalid Tag Name

$ Input: code = "<DIV>>> ![cdata[]] <![CDATA[<div>content</div>]]>></DIV>"

› Output: false

💡 Note: The CDATA section is malformed - it should be but has extra characters.

Example 3 — No Wrapping Tag

$ Input: code = "<A> <B> </A> </B>"

› Output: false

💡 Note: The tags are not properly nested. Tag B is opened inside A but closed after A is closed, violating proper nesting rules.

Constraints

1 ≤ code.length ≤ 500
code consists of English letters, digits, '<', '>', '/', '!', '[', ']', '.', and ' '.

Visualization

Tap to expand

Understanding the Visualization

Input Code

String with XML-like tags to validate

Parse Tags

Check tag names, nesting, and CDATA sections

Output Result

Return true if valid, false otherwise

Key Takeaway

🎯 Key Insight: Use a stack to track nested tag structure while treating CDATA as opaque content

Asked in

G Google 15 a Amazon 12

The key insight is to use a stack to track nested tags while handling special CDATA sections that should be skipped entirely. Best approach is stack-based parsing with single pass validation. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Tag Matching	O(n)	O(n)	Use stack to track nested tags and validate proper opening/closing
Character-by-Character Validation	O(n²)	O(1)	Parse each character individually and manually track tag state

Stack-Based Tag Matching — Algorithm Steps

Step 1: Parse tags and push opening tags to stack
Step 2: Skip CDATA sections completely
Step 3: Match closing tags with stack top and pop

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Opening Tags

Add opening tags to stack

Skip CDATA

Ignore content in CDATA sections

Match Closing Tags

Pop stack when closing tag matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

#define MAX_STACK_SIZE 1000

typedef struct {
    char tags[MAX_STACK_SIZE][10];
    int top;
} TagStack;

void initStack(TagStack* stack) {
    stack->top = -1;
}

void push(TagStack* stack, const char* tag) {
    stack->top++;
    strcpy(stack->tags[stack->top], tag);
}

void pop(TagStack* stack) {
    if (stack->top >= 0) {
        stack->top--;
    }
}

char* peek(TagStack* stack) {
    if (stack->top >= 0) {
        return stack->tags[stack->top];
    }
    return NULL;
}

bool isEmpty(TagStack* stack) {
    return stack->top == -1;
}

bool isValidTagName(const char* name, int len) {
    if (len < 1 || len > 9) return false;
    for (int i = 0; i < len; i++) {
        if (!isupper(name[i]) || !isalpha(name[i])) return false;
    }
    return true;
}

bool solution(char* code) {
    if (!code || strlen(code) == 0 || code[0] != '<') {
        return false;
    }
    
    TagStack stack;
    initStack(&stack);
    int i = 0;
    int len = strlen(code);
    
    while (i < len) {
        if (i + 9 <= len && strncmp(code + i, "<![CDATA[", 9) == 0) {
            // Handle CDATA section
            if (isEmpty(&stack)) { // CDATA must be inside tags
                return false;
            }
            char* cdataEnd = strstr(code + i + 9, "]]>");
            if (!cdataEnd) {
                return false;
            }
            i = cdataEnd - code + 3;
        } else if (code[i] == '<') {
            if (i + 1 < len && code[i + 1] == '/') {
                // Closing tag
                char* closePos = strchr(code + i + 2, '>');
                if (!closePos) {
                    return false;
                }
                int tagLen = closePos - (code + i + 2);
                char tagName[10];
                strncpy(tagName, code + i + 2, tagLen);
                tagName[tagLen] = '\0';
                
                char* topTag = peek(&stack);
                if (!topTag || strcmp(topTag, tagName) != 0) {
                    return false;
                }
                pop(&stack);
                i = closePos - code + 1;
            } else {
                // Opening tag
                char* closePos = strchr(code + i + 1, '>');
                if (!closePos) {
                    return false;
                }
                int tagLen = closePos - (code + i + 1);
                if (!isValidTagName(code + i + 1, tagLen)) {
                    return false;
                }
                char tagName[10];
                strncpy(tagName, code + i + 1, tagLen);
                tagName[tagLen] = '\0';
                push(&stack, tagName);
                i = closePos - code + 1;
            }
        } else {
            // Regular character
            if (isEmpty(&stack)) { // Content must be inside tags
                return false;
            }
            i++;
        }
    }
    
    return isEmpty(&stack);
}

int main() {
    char code[10000];
    fgets(code, sizeof(code), stdin);
    code[strcspn(code, "\n")] = 0;
    
    bool result = solution(code);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string with constant time stack operations

✓ Linear Growth

Space Complexity

O(n)

Stack stores at most n/2 opening tags in worst case

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Tag Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler