<p><strong>HTML entity parser</strong> is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.</p>

<p>The special characters and their entities for HTML are:</p>

<ul>
	<li><strong>Quotation Mark:</strong> the entity is <code>&amp;quot;</code> and symbol character is <code>&quot;</code>.</li>
	<li><strong>Single Quote Mark:</strong> the entity is <code>&amp;apos;</code> and symbol character is <code>&#39;</code>.</li>
	<li><strong>Ampersand:</strong> the entity is <code>&amp;amp;</code> and symbol character is <code>&amp;</code>.</li>
	<li><strong>Greater Than Sign:</strong> the entity is <code>&amp;gt;</code> and symbol character is <code>&gt;</code>.</li>
	<li><strong>Less Than Sign:</strong> the entity is <code>&amp;lt;</code> and symbol character is <code>&lt;</code>.</li>
	<li><strong>Slash:</strong> the entity is <code>&amp;frasl;</code> and symbol character is <code>/</code>.</li>
</ul>

<p>Given the input <code>text</code> string to the HTML parser, you have to implement the entity parser.</p>

<p>Return <em>the text after replacing the entities by the special characters</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;&amp;amp; is an HTML entity but &amp;ambassador; is not.&quot;
<strong>Output:</strong> &quot;&amp; is an HTML entity but &amp;ambassador; is not.&quot;
<strong>Explanation:</strong> The parser will replace the &amp;amp; entity by &amp;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;and I quote: &amp;quot;...&amp;quot;&quot;
<strong>Output:</strong> &quot;and I quote: \&quot;...\&quot;&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= text.length &lt;= 10<sup>5</sup></code></li>
	<li>The string may contain any possible characters out of all the 256 ASCII characters.</li>
</ul>

# def find_parse(text: str, start: int) -> tuple[bool, int, int]:
#         """start: inclusive"""
#         new_start = text.find('&', start)
#         parse_flag = True
#         if new_start == -1:
#             parse_flag = False
#             new_start = len(text)
#             new_end = len(text) - 1
#         else:
#             # find ;
#             new_end = text.find(';', new_start)
#             if new_end == -1:
#                 parse_flag = False
#                 new_start = len(text)
#                 new_end = len(text) - 1
#             else:
#                 parse_flag = True

#         return parse_flag, new_start, new_end

# def find_parse(text: str, start: int, chars: str) -> tuple[bool, int, int]:
#         """start: inclusive"""
#         new_start = text.find(chars, start)
#         parse_flag = True
#         # if new_start == -1:
#         #     parse_flag = False
#         #     new_start = len(text)
#         #     new_end = len(text) - 1
#         # else:
#         #     # find ;
#         #     new_end = text.find(';', new_start)
#         #     if new_end == -1:
#         #         parse_flag = False
#         #         new_start = len(text)
#         #         new_end = len(text) - 1
#         #     else:
#         #         parse_flag = True

#         # return parse_flag, new_start, new_end

def find_all_char(text: str, special_char: str, special_char_index: list[tuple[int, int, str]]) -> None:
    # (begin, end, special_char)
    # special_char_index = []
    # append each special char
    start = 0
    len_text = len(text)
    while start < len_text:
        new_start = text.find(special_char, start)        
        if new_start == -1:
            return
        new_end = text.find(';', new_start)
        # append
        special_char_index.append((new_start, new_end, special_char))      
        start = new_end + 1


# from collections import defaultdict
class Solution:
    def entityParser(self, text: str) -> str:
        """
        find matching character begin with & and end with ;
        parsed word check, and replace with 

        may be by each special char?
        """
        char_map = {
            '&quot;': "\"", '&apos;': "\'", '&amp;': '&', '&gt;': '>',
            '&lt;': '<', '&frasl;': '/',
        }
        existing_special_char = set()
        for special_char in char_map.keys():
            if special_char in text:
                existing_special_char.add(special_char) 
        if len(existing_special_char) == 0:
            return text
        # only consider existing_special_char (begin)
        # (begin, end, special_char)
        special_char_index = []
        for special_char in existing_special_char:
            # find all special_char
            find_all_char(text, special_char, special_char_index)        
        # sort by index
        special_char_index.sort()

        # replace
        # list of parsed
        parsed_text_list = []
        prev_start = 0
        for start, end, special_char in special_char_index:
            # previous
            parsed_text_list.append(text[prev_start:start])
            # replace
            parsed_text_list.append(char_map[special_char])
            # update prev_start
            prev_start = end + 1
        # remainig
        if prev_start < len(text):
            # previous
            parsed_text_list.append(text[prev_start:])

        return ''.join(parsed_text_list)

        
        
            


        


        



        # # (begin, end)        
        # # iteratively
        # start = 0
        # len_text = len(text)
        # end = len_text - 1
        # # list of parsed
        # parsed_text_list = []
        # # list of concatenated
        # while start < len_text:            
        #     prev_start = start
        #     # TODO: if parse_flag is False, end is the last sequence
        #     parse_flag, start, end = find_parse(text, start)
        #     # previous text
        #     parsed_text_list.append(text[prev_start:start])
        #     if parse_flag:
        #         special_char = text[start: end + 1]
        #         # match
        #         if special_char in char_dict:
        #             # replace with 
        #             # TODO
        #             parsed_text_list.append(char_dict[special_char])                    
        #         else:
        #             parsed_text_list.append(special_char)
        #         # for the next
        #         start = end + 1
        # return ''.join(parsed_text_list)


                
        

98