C++ two-pointers O(n) | O(1)
We can use two-pointers approach and re-use the input string to store the output:\n- Copy the current character text[p] = text[i]\n- Track the starting position
We can use two-pointers approach and re-use the input string to store the output:\n- Copy the current character `text[p] = text[i]`\n- Track the starting position of \'&\'\n- When we see `\';\'`, check for the special character.\n\t- For a match, decrease the slow pointer `p`, and copy the corresponding symbol.\n\nFor true O(n) solution, we need to use Trie to do the matching. I feel lazy today so I just broke special characters by size to minimize checks.\n> **Update:** see below for Trie-based, true O(n) solution.\n\n```cpp\nstring entityParser(string text) {    \n    vector<pair<string,char>> encoded[8] = {{}, {}, {}, {}, {{"&gt;", \'>\'}, {"&lt;", \'<\'}},\n        {{"&amp;", \'&\'}}, {{"&quot;", \'"\'}, {"&apos;", \'\\\'\'}}, {{"&frasl;", \'/\'}}};\n    int st = 0, p = 0;\n    for (auto i = 0; i < text.size(); ++i, ++p) {\n        text[p] = text[i];\n        if (text[p] == \'&\')\n            st = p;\n        if (text[p] == \';\') { \n            auto sz = p - st + 1;\n            if (sz >= 4 && sz <= 7)\n                for (auto &[enc, dec] : encoded[sz]) {\n                    if (text.compare(st, sz, enc) == 0) {\n                        p = st;\n                        text[p] = dec;\n                        break;\n                    }\n                }\n            st = p + 1;\n        }\n    }\n    text.resize(p);\n    return text;\n}\n```\n#### True O(n) Solution\n```cpp\nstruct Trie {\n    Trie * chars[26] = {};\n    char symbol = 0;\n    void insert(string &w, char ch, int p = 0) {\n        if (p == w.size())\n            symbol = ch;\n        else {\n            if (chars[w[p] - \'a\'] == nullptr)\n                chars[w[p] - \'a\'] = new Trie();\n            chars[w[p] - \'a\']->insert(w, ch, p + 1);\n        }\n    }\n    char check(string &w, int p, int sz) {\n        if (sz == 0 && symbol != 0)\n            return symbol;\n        if (w[p] < \'a\' || w[p] > \'z\' || chars[w[p] - \'a\'] == nullptr)\n            return 0;\n        return chars[w[p] - \'a\']->check(w, p + 1, sz - 1);\n    }\n};\nvector<pair<string, char>> special = {{"gt", \'>\'}, {"lt", \'<\'},\n    {"amp", \'&\'}, {"quot", \'"\'}, {"apos", \'\\\'\'}, {"frasl", \'/\'}};\nstring entityParser(string &text) {\n    Trie root;\n    for (auto &[str, ch] : special)\n        root.insert(str, ch);\n    int st = 0, p = 0;\n    for (auto i = 0; i < text.size(); ++i, ++p) {\n        text[p] = text[i];\n        if (text[p] == \'&\')\n            st = p;\n        if (text[p] == \';\') {\n            auto ch = root.check(text, st + 1, p - st - 1);\n            if (ch != 0) {\n                p -= p - st;\n                text[p] = ch;\n            }\n            st = p + 1;\n        }\n    }\n    text.resize(p);\n    return text;\n}\n```
[]