You are given a string containing text and HTML-style tags (e.g., <div>, <p>, </div>). Your task is to determine if the "labels" or "tags" are correctly balanced.

• Opening Tags: Stored as <tagname>.

• Closing Tags: Stored as </tagname>.

• Goal: Every opening tag must have a corresponding closing tag of the same word, and they must be closed in the reverse order they were opened (Last-In, First-Out).

Example 1 (Valid): "<div><p>Hello World</p></div>"

• <div> opens.

• <p> opens.

• </p> matches the last opened tag (p).

• </div> matches the first opened tag (div).

Example 2 (Invalid): "<div><p>Hello World</div></p>"

• The div is closed before the p, which violates the nesting rules.

How to Solve It (Algorithm)

To solve this efficiently, you use a Stack data structure:

1. Traverse the string and find every occurrence of a tag (text between < and >).

2. If it's an opening tag (e.g., <b>): Push the word (e.g., "b") onto the stack.

3. If it's a closing tag (e.g., </b>):

   • Check if the stack is empty. If it is, the string is invalid (closing tag with no opener).

   • Pop the top element from the stack.

   • Compare the popped word with the word in the closing tag. If they are not the same word, the string is invalid.

4. Final Check: After parsing the entire string, the stack must be empty. If there are still words in the stack, it means some tags were never closed.

Example Logic Walkthrough

For the input: <div><span></span>

• Step 1: Encounter div. Stack: ['div']

• Step 2: Encounter span. Stack: ['div', 'span']

• Step 3: Encounter /span. Pop span. Does span == span? Yes. Stack: ['div']

• Result: String ends, but stack is not empty. Output: Invalid (or the name of the unclosed tag).

Common Variations

• Self-closing tags: Some versions ask you to ignore tags like <img /> or <br /> which do not require a closing counterpart.

• Return Value: Some versions ask for a boolean (true/false), while others ask you to return the name of the first tag that breaks the sequence.

 1 def check_html_labels(html_string):
 2     stack = []
 3     i = 0
 4     n = len(html_string)
 5     
 6     while i < n:
 7         # 1. Find the start of a tag
 8         if html_string[i] == '<':
 9             # Find the closing bracket for this tag
10             end_idx = html_string.find('>', i)
11             if end_idx == -1:
12                 break # Malformed HTML
13             
14             # Extract the content (e.g., "div" or "/div")
15             full_tag = html_string[i+1:end_idx]
16             
17             # Update loop index to continue after the '>'
18             i = end_idx + 1
19             
20             # 2. Handle Closing Tags
21             if full_tag.startswith('/'):
22                 tag_name = full_tag[1:]
23                 if not stack or stack[-1] != tag_name:
24                     return tag_name # Mismatch found
25                 stack.pop()
26             
27             # 3. Handle Opening Tags
28             else:
29                 # Handle potential attributes: <div class="test"> -> "div"
30                 tag_name = full_tag.split()[0]
31                 # Ignore self-closing tags like <br/>
32                 if not tag_name.endswith('/'):
33                     stack.append(tag_name)
34         else:
35             # Not a tag, just move to the next character
36             i += 1
37             
38     # Final check: If stack is empty, it's valid.
39     return True if not stack else stack[-1]
40 
41 # --- Test Cases ---
42 print(f"Result 1: {check_html_labels('<div><p>Valid</p></div>')}")  # True
43 print(f"Result 2: {check_html_labels('<div><span>Error</div>')}")   # span (it was never closed)
44 print(f"Result 3: {check_html_labels('<b><i>Mismatch</b></i>')}")    # i (b tried to close while i was top)