Beats 💯 | Easy solution | ✅ nLogn | Heap
Intuition\n Describe your first thoughts on how to solve this problem. \nIn this problem we just need to pay attention on two points \n 1. smallest character oc
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn this problem we just need to pay attention on two points \n 1. smallest character occuring before *****.\n 2. smallest the removal of character should be of highest index if theres a repeatition of same characters before a *****.\n \nSince we need to remove characters based from string S based on the above  observations, **PrioirityQueue(Min Heap)** comes in the picture cause \n1. It can sort the characters in an ascending order.\n2. It can also sort the characters based on their indices if the characters are repeated. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n Lets discuss the approach.\n we can use a class Pair or array of int[] to store each characters and their indices in priorityQueue.\n 1.  Traverse the loop and check if the current character is a ***** then don\'t push in the PQ, just remove the top character from the PQ if the PQ is not empty.\n 2. To Store the characters left in the PQ we\'ll use **ArrayList** and then jus sort it based on their indices to get the correct ordering of the characters.\n 3. Traverse the list and store the characters in the StringBuilder and return it.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n**nlogn**\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nconstant O(n^2)\n# Code\n```\n   class Pair{\n        char c;\n        int ind;\n       public Pair(char c,int ind){\n           this.c=c;\n           this.ind=ind;\n       }\n    }\nclass Solution {\n    public String clearStars(String s) {\n         PriorityQueue<Pair>pq=new PriorityQueue<>((a,b)->{\n            if(a.c!=b.c){\n                return a.c-b.c;\n            }\n            else{\n                return b.ind-a.ind;\n            }\n        });\n        int i=0;\n        for(char ch:s.toCharArray()){\n            if(ch==\'*\'){\n              if(!pq.isEmpty()){\n                  pq.poll();\n              }\n            }else{\n                pq.offer(new Pair(ch,i));\n            }\n            i++;\n        }\n        ArrayList<Pair>list=new ArrayList<>();\n        while(!pq.isEmpty()){\n            list.add(pq.poll());\n        }\n        Collections.sort(list,(a,b)->a.ind-b.ind);\n        StringBuilder sb=new StringBuilder();\n        for(Pair num:list){\n          sb.append(num.c);\n        }\n        return sb.toString();\n    }\n}\n```
['Sorting', 'Heap (Priority Queue)', 'Java']