Lexicographically Minimum String After Removing Stars
Source: leetcode
Difficulty: Medium
Tags: hash-table, string, stack, greedy, heap-priority-queue

You are given a string `s`. It may contain any number of `'*'` characters. Your task is to remove all `'*'` characters.


While there is a `'*'`, do the following operation:


- Delete the leftmost `'*'` and the **smallest** non\-`'*'` character to its *left*. If there are several smallest characters, you can delete any of them.


Return the lexicographically smallest resulting string after removing all `'*'` characters.


 


**Example 1:**



**Input:** s \= "aaba\*"


**Output:** "aab"


**Explanation:**


We should delete one of the `'a'` characters with `'*'`. If we choose `s[3]`, `s` becomes the lexicographically smallest.



**Example 2:**



**Input:** s \= "abc"


**Output:** "abc"


**Explanation:**


There is no `'*'` in the string.



 


**Constraints:**


- `1 <= s.length <= 105`
- `s` consists only of lowercase English letters and `'*'`.
- The input is generated such that it is possible to delete all `'*'` characters.




C++ solution:
class Solution {
public:
    string clearStars(string s) {
        vector<vector<int>>arr(26);
        vector<int> ind;
        for(int i = 0 ; i < s.size(); i++){
            if(s[i] != '*') arr[s[i]-'a'].push_back(i);
            else{
                for(int j = 0; j < 26; j++){
                    if(arr[j].size()) {
                        arr[j].pop_back();
                        break;
                    }
                }
            }
        }
        for(int j = 0; j < 26; j++){
            for(int k = 0; k < arr[j].size();  k++){
                ind.push_back(arr[j][k]);
            }
        }
        sort(ind.begin(), ind.end());
        string ans = "";
        for(auto it: ind) ans.push_back(s[it]);
        return ans;
    }
};

Go solution:
func clearStars(s string) string {
    t := []byte(s)
    n := len(s)

    pos := [26][]int{}

    for i := 0; i < n; i++ {
        if t[i] != '*' {
            c := t[i]-'a'
            pos[c] = append(pos[c], i)
            continue
        }
        var c int
        for c = 0; c < 26; c++ {
            if len(pos[c]) > 0 { break }
        }
        p := pos[c][len(pos[c])-1]
        pos[c] = pos[c][:len(pos[c])-1]
        t[p] = '*'
    }
    tt := make([]byte, 0, n)
    for i := 0; i < n; i++ {
        if t[i] == '*' { continue }
        tt = append(tt, t[i])
    }
    return string(tt)
}

Java solution:
class Solution {
    public String clearStars(String s){
        int n = s.length();
        
        List<List<Integer>> buckets = new ArrayList<>();
        
        for(int i = 0; i < 26; i++){
            buckets.add(new ArrayList<>());
        }
        
        boolean[] removed = new boolean[n];
        
        for (int i = 0 ; i < n ; i++){
            if(s.charAt(i) == '*'){
                removed[i] = true;
                for (int j = 0; j < 26; j++){
                    if (!buckets.get(j).isEmpty()){
                        removed[buckets.get(j).get(buckets.get(j).size() - 1)] = true;
                        buckets.get(j).remove(buckets.get(j).size() - 1);
                        break;
                    }
                }
            } 
            else{
                buckets.get(s.charAt(i) - 'a').add(i);
            }
        }
        
        StringBuilder ans = new StringBuilder();
        for(int i = 0 ; i < n ; i++){
            if(!removed[i]) ans.append(s.charAt(i));
        }
        return ans.toString();
    }
}

JavaScript solution:
/**
 * @param {string} s
 * @return {string}
 */
var clearStars = function(s) {
    const mp = new Map();
        const n = s.length;
        const v = new Array(n).fill(0);

        for (let i = 0; i < n; i++) {
            if (s[i] !== '*') {
                if (!mp.has(s[i])) {
                    mp.set(s[i], []);
                }
                mp.get(s[i]).push(i);
            } else {
                v[i] = 1;
                const sortedEntries = Array.from(mp.entries()).sort((a, b) => a[0].localeCompare(b[0]));
                for (let [key, indices] of sortedEntries) {
                    const m = indices.length;
                    v[indices[m - 1]] = 1;
                    indices.pop();
                    if (indices.length === 0) {
                        mp.delete(key);
                    }
                    break;
                }
            }
        }

        let ans = "";
        for (let i = 0; i < n; i++) {
            if (v[i] !== 1) {
                ans += s[i];
            }
        }
        return ans;
};

Python solution:
class Solution:
    def clearStars(self, s: str) -> str:
        heap = []
        charIndex = defaultdict(list)
        s = list(s)
        for i, c in enumerate(s):
            if c == "*":
                toRemove = heap[0]
                s[charIndex[toRemove].pop()] = ""
                if not charIndex[toRemove]: heappop(heap)
                s[i] = ""
            else:
                if len(charIndex[c]) == 0:
                    heappush(heap, c)
                charIndex[c].append(i)
        return "".join(s)

Ruby solution:
def clear_stars(s)
    buckets = Array.new(26) { [] }
    s.each_char.with_index do |c, i|
        if c == '*'
            (0..25).each do |j|
                unless buckets[j].empty?
                    buckets[j].pop
                    break
                end
            end
        else
            idx = c.ord - 'a'.ord
            buckets[idx] << i
        end
    end
    remaining = []
    buckets.each { |bucket| remaining += bucket }
    remaining.sort.map { |i| s[i] }.join
end