<p>Given a string <code>s</code>, find the <strong>first</strong> non-repeating character in it and return its index. If it <strong>does not</strong> exist, return <code>-1</code>.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;leetcode&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p>The character <code>&#39;l&#39;</code> at index 0 is the first character that does not occur at any other index.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;loveleetcode&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;aabb&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>
</div>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

template<typename T>
class LinkedListNode {
    public:
    T data;
    LinkedListNode<T>* next;
    LinkedListNode<T>* prev;

    LinkedListNode(T data, LinkedListNode<T>* next=nullptr, LinkedListNode<T>* prev=nullptr) : data(data), next(next), prev(prev){}
    LinkedListNode() = default;

    static void deleteNode(LinkedListNode<T>* node) {
        if (!node) return;
        if (node->prev) {
            node->prev->next = node->next;
        }
        if (node->next) {
            node->next->prev = node->prev;
        }
        delete node;
    }

    static void printList(LinkedListNode<T>* head) {
        while (head) {
            cout << head->data;
            cout << (head->next ? " " : "\n");
            head = head->next;
        }
    }
};

class Solution {
public:
    int firstUniqChar(const string& s) {
        typedef LinkedListNode<int> IntLinkedListNode;
        typedef LinkedListNode<int>* IntLinkedListNodePtr;
        IntLinkedListNodePtr head = new IntLinkedListNode();
        IntLinkedListNodePtr mover = head;
        unordered_map<int, IntLinkedListNodePtr> uniqueOrder;
        int hash[26] = {0};
        for (int i = 0 ; i < s.length(); i++) {
            int currChar = s[i]-'a';
            if (hash[currChar]) {
                const auto it = uniqueOrder.find(currChar);
                if (it != uniqueOrder.end()) {
                    if (mover == it->second) {
                        mover = mover->prev;
                    }
                    IntLinkedListNode::deleteNode(it->second);
                    uniqueOrder.erase(currChar);
                }
            }
            else{
                hash[currChar] = 1;
                mover->next = new IntLinkedListNode(i, nullptr, mover);
                uniqueOrder[currChar] = mover->next;
                mover = mover->next;
            }
        }
        return head->next ? head->next->data : -1;
    }
};
12500