HTML Entity Parser - Practice Coding Problems

HTML Entity Parser - Problem

HTML entity parser is the parser that takes HTML code as input and replaces all the entities of the special characters by the characters themselves.

The special characters and their entities for HTML are:

Quotation Mark: the entity is " and symbol character is "
Single Quote Mark: the entity is ' and symbol character is '
Ampersand: the entity is & and symbol character is &
Greater Than Sign: the entity is > and symbol character is >
Less Than Sign: the entity is < and symbol character is <
Slash: the entity is &frasl; and symbol character is /

Given an input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Input & Output

Example 1 — Basic Entities

$ Input: text = "& is an HTML entity but &ambassador; is not."

› Output: "& is an HTML entity but &ambassador; is not."

💡 Note: & is a valid entity that gets replaced with &, but &ambassador; is not a valid HTML entity so it stays unchanged

Example 2 — Multiple Entities

$ Input: text = "and I quote: "...""

› Output: "and I quote: \"...\""

💡 Note: " entities are replaced with quotation marks to form: and I quote: "..."

Example 3 — No Valid Entities

$ Input: text = "Stay home! Practice on Leetcode :)"

› Output: "Stay home! Practice on Leetcode :)"

💡 Note: No HTML entities present, so the string remains unchanged

Constraints

1 ≤ text.length ≤ 10⁵
The string may contain any possible characters out of all the 256 ASCII characters.

Visualization

Tap to expand

Understanding the Visualization

Input

HTML text with entities like &, >, "

Parse

Identify and replace valid HTML entities

Output

Clean text with actual characters

Key Takeaway

🎯 Key Insight: Use hash map for O(1) entity lookup during single string traversal

Asked in

a Amazon 15 f Facebook 12 G Google 8 M Microsoft 6

The key insight is to use a hash map for O(1) entity lookup while scanning the string once. When encountering '&', check if a valid entity starts there. Best approach is single pass with hash map. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass with Hash Map	O(n)	O(1)	Use hash map for O(1) lookup while scanning string once
Multiple String Replacements	O(n × k)	O(n)	Replace each entity type one by one using built-in string replace

Single Pass with Hash Map — Algorithm Steps

Create hash map of entities to characters
Scan string character by character
When '&' found, check if valid entity starts there
Replace entity or keep original character

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set up hash map and result builder

Scan & Check

When '&' found, check hash map for valid entity

Replace or Keep

Replace entity or keep original character

Code -

solution.c — C

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

char* solution(char* text) {
    char* entities[] = {"&quot;", "&apos;", "&amp;", "&gt;", "&lt;", "&frasl;"};
    char* chars[] = {"\"", "'", "&", ">", "<", "/"};
    
    int len = strlen(text);
    char* result = (char*)malloc(len + 1);
    int j = 0;
    
    for (int i = 0; i < len; ) {
        if (text[i] == '&') {
            int found = 0;
            for (int k = 0; k < 6; k++) {
                int entity_len = strlen(entities[k]);
                if (strncmp(&text[i], entities[k], entity_len) == 0) {
                    strcpy(&result[j], chars[k]);
                    j += strlen(chars[k]);
                    i += entity_len;
                    found = 1;
                    break;
                }
            }
            if (!found) {
                result[j++] = text[i++];
            }
        } else {
            result[j++] = text[i++];
        }
    }
    
    result[j] = '\0';
    return result;
}

int main() {
    char text[10000];
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = 0;
    
    char* result = solution(text);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string, hash map lookup is O(1)

✓ Linear Growth

Space Complexity

O(1)

Hash map stores only 6 entities, result string space

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

890 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

Single Pass with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler