O(N * 26) | Simple Greedy Solution | C++ | Java | Python
Approach -\n- When ever we encounter  \'*\' , we need to remove the smallest character on the left of  \'*\' \n- The Problem rises when there are multiple occur
# Approach -\n- When ever we encounter  `\'*\'` , we need to remove the smallest character on the left of  `\'*\'` \n- The Problem rises when there are multiple occurences of smallest character \n- Here we can `greedily remove the rightmost occurence of the smallest character` on the left of `\'*\'` \n- This is because , removing the smallest character at any other postion , might pull the larger characters to the left , which will not be lexicographically smallest.\n# Code Explanation - \n- `Buckets` - of size 26 to keep track of positions of each character\n- `Removed` - For marking positions of removed characters\n- Whenever we find ` \'*\' ` , we will remove (mark as removed) the rightmost occurence of smallest character\n- Else we\'ll keep updating buckets for each character.\n- Finally we construct our resultant string using Removed array\n# Complexity - \n- Time Complexity - O(N * 26)\n- Space Complecity - O(N)\n```C++ []\nclass Solution {\npublic:\n    string clearStars(string s){\n        int n = s.size();\n        vector<vector<int>> buckets(26);\n        vector<int> removed(n , 0);\n        for(int i = 0 ; i < n ; i++){\n            if(s[i] == \'*\'){\n                removed[i] = 1;\n                for(int j = 0 ; j < 26 ; j++){\n                    if(buckets[j].size()){\n                        removed[buckets[j].back()] = 1;\n                        buckets[j].pop_back();\n                        break;\n                    }\n                }\n            }\n            else{\n                buckets[s[i]-\'a\'].push_back(i);\n            }\n        }\n        string ans;\n        for(int i = 0 ; i < n ; i++){\n            if(!removed[i]) ans.push_back(s[i]);\n        }\n        return ans;\n    }\n};\n```\n```Java []\n\nclass Solution {\n    public String clearStars(String s){\n        int n = s.length();\n        \n        List<List<Integer>> buckets = new ArrayList<>();\n        \n        for(int i = 0; i < 26; i++){\n            buckets.add(new ArrayList<>());\n        }\n        \n        boolean[] removed = new boolean[n];\n        \n        for (int i = 0 ; i < n ; i++){\n            if(s.charAt(i) == \'*\'){\n                removed[i] = true;\n                for (int j = 0; j < 26; j++){\n                    if (!buckets.get(j).isEmpty()){\n                        removed[buckets.get(j).get(buckets.get(j).size() - 1)] = true;\n                        buckets.get(j).remove(buckets.get(j).size() - 1);\n                        break;\n                    }\n                }\n            } \n            else{\n                buckets.get(s.charAt(i) - \'a\').add(i);\n            }\n        }\n        \n        StringBuilder ans = new StringBuilder();\n        for(int i = 0 ; i < n ; i++){\n            if(!removed[i]) ans.append(s.charAt(i));\n        }\n        return ans.toString();\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def clearStars(self, s: str) -> str:\n        n = len(s)\n        buckets = [[] for _ in range(26)]\n        removed = [False] * n\n        \n        for i in range(n):\n            if s[i] == \'*\':\n                removed[i] = True\n                for j in range(26):\n                    if buckets[j]:\n                        removed[buckets[j].pop()] = True\n                        break\n            else:\n                buckets[ord(s[i]) - ord(\'a\')].append(i)\n        \n        result = []\n        for i in range(n):\n            if not removed[i]:\n                result.append(s[i])\n        \n        return \'\'.join(result)\n```\n
['Greedy', 'C++', 'Java', 'Python3']