[JAVA] O(N) solution
Intuition\n Describe your first thoughts on how to solve this problem. \n1. Keep track of the positions of all letters\n2. Once a * is encountered, find the fir
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. Keep track of the positions of all letters\n2. Once a `* ` is encountered, find the first letter alphabetically and remove the last position. Save the removed position to a set.\n3. Loop string again and ignore the removed letters and stars\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(26 * N) -> O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public String clearStars(String s) {\n        List<Integer>[] map = new ArrayList[26];\n        Set<Integer> set = new HashSet<>();\n        for (int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if (c != \'*\') {\n                if (map[c - \'a\'] == null) {\n                    map[c - \'a\'] = new ArrayList<Integer>();\n                }\n                map[c - \'a\'].add(i);\n            } else {\n                for (int j = 0; j < 26; j++) {\n                    if (map[j] == null || map[j].size() == 0) continue;\n                    set.add(map[j].get(map[j].size() - 1));\n                    map[j].remove(map[j].size() - 1);\n                    break;\n                }\n            }\n        }\n        \n        var sb = new StringBuilder();\n        for (int i = 0; i < s.length(); i++) {\n            if (set.contains(i) || s.charAt(i) == \'*\') continue;\n            sb.append(s.charAt(i));\n        }\n        return sb.toString();\n    }\n}\n```
['Java']