Java | Easy | Priority Queue
Intuiton:\nIf you look closely, this problem is a problem of priority queue and how well you handle a string. The queue is made on two criteria:\n it takes in a
**Intuiton**:\nIf you look closely, this problem is a problem of priority queue and how well you handle a string. The queue is made on two criteria:\n* it takes in a variable *pri* with character and integer as attributes. First it sorts all the characters it takes in pri in lexicographical order. This we achieve by` Character.compare(a.let, b.let)`\n* If characters are same, I need the nearest of them (nearest to the * ) to make the end string lexicographically smallest. Since I will be traversing the string left to right, I will be storing the indices of where the characters have occured in the other attribute of class pri. This I have to sort in decreasing order. When indices stored as int are arranged in descending order, the closest to the present iterator would get prioritized.\n*Another challenge of this problem is to know that any mutation on string or string-builder while we are still checking where characters have appeared would impact the mutation itself*. In other words, you have to do the two task of collecting indices where characters will be deleted AND the task of deleting such characters separetely. Otherwise indices would go hay-wire.\n\n**Approach**:\n1. Use a priority queue to  do the sorting as required.\n2. Wherever you get a * , retrieve the head of the priority queue and collect the integer index it represent in a list or set\n3. Poll the head as we are done with it.\n4. To build the string, travel through the string in a different loop, and exclude the * and whenever the index appears in the set.\n5. Return the string buildre as string\n\n\n```\n\nclass pri{\n\tint pos;char let;\n\tpri(int pos,char let){\n\t\tthis.pos=pos;\n\t\tthis.let=let;\n\t}\n}\n\n\nclass Solution {\n    public String clearStars(String s) {\n        int pos=-1;char cur;\n\t\t  \tStringBuilder sb=new StringBuilder();\n\t\t    Set<Integer> lt=new HashSet<>();\n\t        PriorityQueue<pri> q=new PriorityQueue<>(new Comparator<pri>() {\n\t        \tpublic int compare(pri a,pri b) {\n\t        \t\tif(Character.compare(a.let, b.let)!=0)\n\t        \t\t\treturn Character.compare(a.let, b.let);\n\t        \t\treturn Integer.compare(b.pos,a.pos);\n\t        \t}\n\t        });\n\t        \n\t        for(int i=0;i<s.length();i++) {  \n\t        \tif(s.charAt(i)!=\'*\') { \n\t        \t\tq.add(new pri(i,s.charAt(i)));\n\t        \t\tpos=q.peek().pos;\n\t        \t\t}\n\t        \telse {\n\t        \t\tlt.add(pos);\n\t        \t\tq.poll();\n\t        \t\tif(!q.isEmpty()) pos=q.peek().pos;\n\t        \t}\n\t        }\n\t        \n\t        for(int i=0;i<s.length();i++) {\n\t        \tif(s.charAt(i)!=\'*\'&&!lt.contains(i))\n\t        \t\tsb.append(s.charAt(i));\n\t        }\n\t        \n\t        return new String(sb);\n    }\n}\n\n```\n\n**Time Complexity**:\nO(N)  We ran through the string twice\n\n**Space Complexity**:\nO(N) for the set
['Java']