Lexicographically Minimum String After Removing Stars

medium stack greedy string

Problem

You are given a string s that may contain '*' characters. While a '*' remains, delete the leftmost '*' together with the smallest non-'*' character somewhere to its left (ties may break either way). Return the lexicographically smallest string left after all stars are removed.

Inputs = "aaba*"

Output"aab"

The '*' must remove an 'a'. Removing the rightmost 'a' (index 3) leaves "aab", the smallest option.

s (lowercase letters and *)

def clearStars(s):
    stacks = [[] for _ in range(26)]   # one index-stack per letter
    removed = [False] * len(s)
    for i, ch in enumerate(s):
        if ch == '*':
            removed[i] = True          # the '*' itself is deleted
            for j in range(26):        # find smallest available letter
                if stacks[j]:
                    removed[stacks[j].pop()] = True  # drop its rightmost
                    break
        else:
            stacks[ord(ch) - 97].append(i)
    return ''.join(s[i] for i in range(len(s)) if not removed[i])

function clearStars(s) {
  const stacks = Array.from({ length: 26 }, () => []); // index-stack per letter
  const removed = new Array(s.length).fill(false);
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (ch === "*") {
      removed[i] = true;                 // delete the '*'
      for (let j = 0; j < 26; j++) {     // smallest available letter
        if (stacks[j].length) {
          removed[stacks[j].pop()] = true; // drop its rightmost
          break;
        }
      }
    } else {
      stacks[ch.charCodeAt(0) - 97].push(i);
    }
  }
  let res = "";
  for (let i = 0; i < s.length; i++) if (!removed[i]) res += s[i];
  return res;
}

String clearStars(String s) {
    List<Integer>[] stacks = new List[26];      // index-stack per letter
    for (int j = 0; j < 26; j++) stacks[j] = new ArrayList<>();
    boolean[] removed = new boolean[s.length()];
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch == '*') {
            removed[i] = true;                   // delete the '*'
            for (int j = 0; j < 26; j++) {       // smallest available letter
                if (!stacks[j].isEmpty()) {
                    removed[stacks[j].remove(stacks[j].size() - 1)] = true;
                    break;
                }
            }
        } else {
            stacks[ch - 'a'].add(i);
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) if (!removed[i]) sb.append(s.charAt(i));
    return sb.toString();
}

string clearStars(string s) {
    vector<vector<int>> stacks(26);        // index-stack per letter
    vector<bool> removed(s.size(), false);
    for (int i = 0; i < (int)s.size(); i++) {
        char ch = s[i];
        if (ch == '*') {
            removed[i] = true;             // delete the '*'
            for (int j = 0; j < 26; j++) { // smallest available letter
                if (!stacks[j].empty()) {
                    removed[stacks[j].back()] = true;
                    stacks[j].pop_back();
                    break;
                }
            }
        } else {
            stacks[ch - 'a'].push_back(i);
        }
    }
    string res;
    for (int i = 0; i < (int)s.size(); i++) if (!removed[i]) res += s[i];
    return res;
}

Explanation

Each '*' erases itself plus one earlier letter, and we get to choose which earlier letter. To make the final string lexicographically smallest, every star should erase the smallest letter still available to its left.

But there is a subtlety: if there are several copies of that smallest letter, which copy should we drop? Among equal letters we want to keep the ones nearer the front, because an early small letter is worth more for lexicographic order. So we delete the rightmost occurrence of that smallest letter.

That "smallest letter, rightmost copy" rule is exactly a stack per letter. We keep 26 stacks, one for each of 'a'..'z', each holding the indices where that letter appeared, in increasing order. Pushing an index puts the newest (rightmost) copy on top.

When we hit a '*', we scan the 26 stacks from 'a' upward, take the first non-empty one (the smallest available letter), and pop its top — the rightmost index of that letter. We mark both that index and the star as removed.

After the pass, we rebuild the answer from the indices that were never removed. Example: "aaba*". Indices 0,1 push to the a-stack, index 2 to b, index 3 to a (stack a is now [0,1,3]). The star at index 4 pops the top of stack a, which is index 3, and removes itself. Surviving indices 0,1,2 spell "aab".

Time: O(n · 26) Space: O(n)