O(n) - min heap with indices vector || with DRY RUN
Intuition \nOnce we reduce the string, all the indices of the string will get messed up! So DON\'T reduce the original string initially.\nInstead, replace the e
## Intuition \nOnce we reduce the string, all the indices of the string **will get messed up**! So **DON\'T reduce** the original string initially.\n*Instead*, replace the elements with something other than English letters. I replaced them with __!__. \n\n## Needed Data Structures\nI) save the characters in a _heap_, i.e. ```priority_queue<char>``` in C++, ```PriorityQueue<Character>``` in Java, ```PriorityQueue()``` in Python.\n\nII) save the character indices in a _vector_ of _vector_, i.e. ```vector<vector<int>>``` in C++, ```ArrayList<ArrayList<Integer>>``` in Java, or ```[[]]``` in Python.\n\n## Approach\nDefine a **priority queue (min heap)** to memorize what is *the smallest character*; save the indices of the characters in a different vector. This is to remove the highest index of the smallest character first. Otherwise, lexiographically, we will have a bigger string. Thus, build the priority_queue **comparison** rule and check the indices vector to make sure it is not empty. If index is empty, then pop from the heap as well.\n\n## Complexity:\n```\nTime: O(n*log(26)) = O(n)  // O(log(26)) maintaining heap; O(n) to iterate the string\nSpace: O(26) + O(2*n) = O(n)  // O(26) heap; O(n) for indices vector and O(n) for result\n```\n## Code\n<iframe src="https://leetcode.com/playground/F7mknzZA/shared" frameBorder="0" width="500" height="700"></iframe>\n\n## Dry run `(skip if you understand the code)`\nThe dryrun below is valid for above __C++__ code. But for __Java__ and __Python__, I use a _HashSet_ instead of in-place string change, so for those two, the below dryrun is only good to an extent. For C++, it is accurate. If you have any problems, ask in the comments.\n\nSuppose `s = "a   a   b  *   d   *  z   d  *"` , then the iterations according to the code is like the following: \n```\nheap state initially: `{}`\nindices vector state initially: `{{}, {} , {}, ....., {} , {}}`\n```\n**Iteration 1:**\n```\n    \uD83D\uDC47\ns = "a   a   b   *   d   *  z   d  *"\n```\n```\nheap: `{a\uD83D\uDC48}`                          \nindices vector: `{{0\uD83D\uDC48}, {} , {} , {}, {}, ....., {} , {}}`\n```\n**Iteration 2:**\n```\n        \uD83D\uDC47\ns = "a   a   b   *   d   *  z   d  *"\n```\n```\nheap: `{a\uD83D\uDC48}`                          \nindices vector: `{{0,1\uD83D\uDC48}, {} , {} , {}, {}, ....., {} , {}}`\n```\n**Iteration 3:**\n```\n            \uD83D\uDC47\ns = "a   a   b   *   d   *  z   d  *"       \n```\n```\nheap: `{a\uD83D\uDC48,b}`                          \nindices vector: `{{0,1\uD83D\uDC48}, {2} , {} , {}, {}, ....., {} , {}}`\n```\n**Iteration 4 (star change):**\n```\n                \uD83D\uDC47\ns = "a   a   b   *   d   *  z   d  *"\n         \uD83D\uDC46(top of the min heap, remove "1" from iv)\n```\nNow, `s = "a ! b * d * z d *" `\n```\nheap: `{a\uD83D\uDC48, b}`                          \nindices vector: `{{0\uD83D\uDC48}, {2} , {} , {}, {}, ....., {} , {}}`\n```\n**Iteration 5:**\n```\n                    \uD83D\uDC47\ns = "a   !   b   *   d   *  z   d  *"\n```\n```\nheap: `{a\uD83D\uDC48, b, d}`                          \nindices vector: `{{0\uD83D\uDC48}, {2} , {} , {4}, {}, ....., {} , {}}`\n```\n**Iteration 6 (star change):**\n```\n                        \uD83D\uDC47\ns = "a   !   b   *   d   *  z   d  *"\n     \uD83D\uDC46(top of the min heap, remove "0" from iv, remove "a" from heap)\n```\nNow, `s = "! ! b * d * z d *" `\n```\nheap: `{b\uD83D\uDC48, d}`                          \nindices vector: `{{}, {2\uD83D\uDC48} , {} , {4}, {}, ....., {} , {}}`\n```\n**Iteration 7:**\n```\n                           \uD83D\uDC47\ns = "!   !   b   *   d   *  z   d  *"\n```\n```\nheap: `{b\uD83D\uDC48, d, z}`                          \nindices vector: `{{}, {2\uD83D\uDC48} , {} , {4}, {}, ....., {} , {6}}`\n```\n**Iteration 8:**\n```\n                              \uD83D\uDC47\ns = "!   !   b  *   d   *  z   d  *"\n```\n```\nheap: `{b\uD83D\uDC48, d, z}`                        \nindices vector: `{{}, {2\uD83D\uDC48} , {} , {4,7}, {}, ....., {} , {6}}`\n```\n**Iteration 9 (star change):**\n```\n                                 \uD83D\uDC47\ns = "!   !   b  *   d   *  z   d  *"\n             \uD83D\uDC46(top of the min heap, remove "2" from iv, remove "b" from heap)\n```\nNow, `s = "! ! ! * d * z d *"`\n```\nheap: `{d\uD83D\uDC48, z}`                                           \nindices vector: `{{}, {} , {} , {4,7\uD83D\uDC48}, {}, ....., {} , {6}}`\n```\n**Iteration Complete:**\n```\ns = "!   !   !  *   d   *  z   d  *"\n                               \uD83D\uDC46(top of the min heap and indices vector, when we finish)\n```\nNow that we finished iterating thru the charachters, filter __!__ and __*__, the resultant string is `d z d`.\n\nFinal __states__ are:\n```\nheap: `{d\uD83D\uDC48, z}`                                           \nindices vector: `{{}, {} , {} , {4,7\uD83D\uDC48}, {}, ....., {} , {6}}`\n```
['Heap (Priority Queue)', 'C++', 'Java', 'Python3']