# Lexicographically Minimum String After Removing Stars
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lexicographically-minimum-string-after-removing-stars)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-minimum-string-after-removing-stars
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Hash Table, String, Stack, Heap (Priority Queue)
**Companies:** [Flexera](https://scaleengineer.com/companies/flexera)
---
## Problem
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.

# Approaches
## Naive Simulation by Repeatedly Modifying the String
This approach directly simulates the process described in the problem. It repeatedly finds the leftmost star, identifies the character to be removed based on the greedy strategy, and reconstructs the string. This process continues until no stars are left.
**Time:** O(N^2), where N is the length of the string. In each of the O(N) iterations (one for each star), finding the star, the smallest character, and its position takes O(N) time. Deletion in a `StringBuilder` also takes O(N). · **Space:** O(N), where N is the length of the string, for storing the `StringBuilder`.
**Pros:** Conceptually simple and easy to follow the problem's description.
**Cons:** Highly inefficient due to repeated scanning and modification of the string.; Will likely result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
In this brute-force method, we use a mutable string representation, like Java's `StringBuilder`, to allow for efficient character deletions. We enter a loop that continues as long as there are `'*'` characters in the string. In each iteration, we locate the first `'*'`. Then, we scan all characters to its left to determine the smallest character. To get the lexicographically smallest final string, we must remove the rightmost occurrence of this smallest character. So, we perform a reverse scan from the star's position to find its index. Finally, we delete both the star and the identified character. This is repeated until all stars are processed.

```java
class Solution {
    public String clearStars(String s) {
        StringBuilder sb = new StringBuilder(s);
        while (true) {
            int starIndex = sb.indexOf("*");
            if (starIndex == -1) {
                break;
            }

            char smallestChar = Character.MAX_VALUE;
            int removeIndex = -1;

            // Find the smallest character to the left of the star
            for (int i = 0; i < starIndex; i++) {
                if (sb.charAt(i) != '*') {
                    smallestChar = (char) Math.min(smallestChar, sb.charAt(i));
                }
            }

            // Find the rightmost occurrence of that smallest character
            for (int i = starIndex - 1; i >= 0; i--) {
                if (sb.charAt(i) == smallestChar) {
                    removeIndex = i;
                    break;
                }
            }
            
            // Delete star first (larger index) to not affect smaller index
            sb.deleteCharAt(starIndex);
            if (removeIndex != -1) {
                sb.deleteCharAt(removeIndex);
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
- Convert the input string `s` to a mutable `StringBuilder`.
- Loop as long as a `'*'` character exists in the `StringBuilder`.
  - Find the index of the leftmost `'*'`. Let this be `starIndex`.
  - If no star is found, exit the loop.
  - Find the smallest character in the substring to the left of the star (`0` to `starIndex - 1`).
  - Find the rightmost index (`removeIndex`) of this smallest character in the same left-side substring.
  - Delete the character at `starIndex` first, then the character at `removeIndex`.
- Convert the `StringBuilder` back to a string and return it.

## Using a Priority Queue to Track Smallest Characters
A more optimized approach is to process the string in a single pass. We can use a Priority Queue to efficiently keep track of the available characters to the left of the current position. The priority queue will be ordered to quickly retrieve the smallest character that appeared most recently (rightmost).
**Time:** O(N log N). Each of the N characters is processed. For letters, we add to the PQ (O(log K) where K is PQ size). For stars, we remove from the PQ (O(log K)). In the worst case, K can be O(N), leading to O(N log N) overall. · **Space:** O(N). The Priority Queue can store up to N elements in the worst case (a string with no stars). The `removed` array also takes O(N) space.
**Pros:** Much faster than the naive approach, passing typical constraints.; Processes the string in a single pass to determine removals.
**Cons:** Slower than the optimal linear time solution due to the logarithmic time complexity of priority queue operations.
### Explanation
The core idea is that for any `'*'`, we must remove the smallest character seen so far. To make the resulting string lexicographically smallest, we should remove the rightmost occurrence of that smallest character. A Priority Queue storing pairs of `(character, index)` is perfect for this. We customize its comparator to sort first by character ('a' before 'b') and then by index in descending order (rightmost first). 

We iterate through the string. When we see a letter, we add a `(character, index)` pair to the priority queue. When we see a `'*'`, we `poll()` from the queue. This gives us the smallest character with its largest index, which is exactly the character we need to remove. We don't modify the string in-place; instead, we mark its original index as 'removed' in a boolean array. After this single pass, we construct the final string by iterating through the original string and appending only the characters that are not stars and not marked as removed.

```java
import java.util.PriorityQueue;

class Solution {
    public String clearStars(String s) {
        class Pair {
            char c;
            int index;
            Pair(char c, int index) {
                this.c = c;
                this.index = index;
            }
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> {
            if (a.c != b.c) {
                return a.c - b.c;
            }
            return b.index - a.index; // Larger index first for ties
        });

        boolean[] removed = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '*') {
                if (!pq.isEmpty()) {
                    Pair toRemove = pq.poll();
                    removed[toRemove.index] = true;
                }
            } else {
                pq.add(new Pair(c, i));
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '*' && !removed[i]) {
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Create a `PriorityQueue` to store pairs of `(character, index)`.
- The priority queue's comparator will prioritize smaller characters, and for ties, larger indices.
- Create a boolean array `removed` of the same size as the input string, initialized to `false`.
- Iterate through the input string `s` with index `i`:
  - If `s[i]` is a letter, add `(s[i], i)` to the priority queue.
  - If `s[i]` is a `'*'`, remove the top element from the priority queue and mark its index in the `removed` array as `true`.
- After the first pass, build the result string by appending characters `s[i]` where `s[i]` is not `'*'` and `removed[i]` is `false`.

## Optimal Single-Pass Solution with Character-Indexed Lists
This is the most efficient approach, achieving linear time complexity. It improves upon the priority queue by using a more specialized data structure: an array of lists (or stacks), one for each character of the alphabet. This allows finding the smallest available character in constant time.
**Time:** O(N). The main loop runs N times. Inside the loop, for letters, it's an O(1) append to a list. For stars, we search for the smallest character, which takes at most 26 steps (a constant, so O(1)). All other operations are O(1). The final string construction is O(N). · **Space:** O(N). The `positions` data structure can store up to N indices in total across all lists. The `removed` array also requires O(N) space.
**Pros:** Optimal O(N) time complexity.; Efficiently implements the greedy strategy in a single pass.
**Cons:** Slightly more complex to implement than the priority queue approach due to managing the array of lists.
### Explanation
Instead of a generic priority queue, we can use an array of 26 lists, where `positions[c-'a']` stores the indices of all occurrences of character `c` seen so far. We iterate through the input string `s`. If `s[i]` is a letter, we add its index `i` to the corresponding list. Since we add indices in increasing order, the last element in any list is always the index of the rightmost occurrence of that character.

If `s[i]` is a `'*'`, we find the smallest character available for removal. We do this by iterating through our `positions` array from index 0 ('a') to 25 ('z'). The first non-empty list corresponds to the smallest character. We then pop the last index from this list and mark it for deletion in a `removed` boolean array. This check for the smallest character takes at most 26 steps, which is a constant time operation.

After this single pass, we construct the final string by collecting all characters from `s` that are not stars and not marked as removed.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public String clearStars(String s) {
        List<List<Integer>> positions = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            positions.add(new ArrayList<>());
        }

        boolean[] removed = new boolean[s.length()];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '*') {
                for (int j = 0; j < 26; j++) { // Find smallest char
                    if (!positions.get(j).isEmpty()) {
                        List<Integer> indices = positions.get(j);
                        int indexToRemove = indices.remove(indices.size() - 1);
                        removed[indexToRemove] = true;
                        break;
                    }
                }
            } else {
                positions.get(c - 'a').add(i);
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '*' && !removed[i]) {
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }
}
```
### Algorithm
- Create an array of 26 lists, `positions`, to store indices for each character 'a' through 'z'.
- Create a boolean array `removed` of size `s.length()`, initialized to `false`.
- Iterate through the input string `s` with index `i`:
  - If `s[i]` is a letter `c`, add `i` to the list `positions[c-'a']`.
  - If `s[i]` is a `'*'`, find the smallest `j` from 0 to 25 such that `positions[j]` is not empty.
    - Remove the last index from `positions[j]` (this is the rightmost occurrence).
    - Mark this index as `true` in the `removed` array.
    - Break the inner loop and continue to the next character of `s`.
- Build the final result string by appending characters `s[i]` where `s[i]` is not `'*'` and `removed[i]` is `false`.

# Solutions
### CSharp

```csharp
public class Solution {
    public string ClearStars(string s) {
        int n = s.Length;
        List < int > [] g = new List < int > [26];
        for (int i = 0; i < 26; i++) {
            g[i] = new List < int > ();
        }
        bool[] rem = new bool[n];
        for (int i = 0; i < n; i++) {
            char ch = s[i];
            if (ch == '*') {
                rem[i] = true;
                for (int j = 0; j < 26; j++) {
                    if (g[j].Count > 0) {
                        int idx = g[j][g[j].Count - 1];
                        g[j].RemoveAt(g[j].Count - 1);
                        rem[idx] = true;
                        break;
                    }
                }
            } else {
                g[ch - 'a'].Add(i);
            }
        }
        var ans = new System.Text.StringBuilder();
        for (int i = 0; i < n; i++) {
            if (!rem[i]) {
                ans.Append(s[i]);
            }
        }
        return ans.ToString();
    }
}
```

### Java

```java
class Solution {
public
  String clearStars(String s) {
    Deque<Integer>[] g = new Deque[26];
    Arrays.setAll(g, k->new ArrayDeque<>());
    int n = s.length();
    boolean[] rem = new boolean[n];
    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '*') {
        rem[i] = true;
        for (int j = 0; j < 26; ++j) {
          if (!g[j].isEmpty()) {
            rem[g[j].pop()] = true;
            break;
          }
        }
      } else {
        g[s.charAt(i) - 'a'].push(i);
      }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; ++i) {
      if (!rem[i]) {
        sb.append(s.charAt(i));
      }
    }
    return sb.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string clearStars(string s) {
    stack<int> g[26];
    int n = s.length();
    vector<bool> rem(n);
    for (int i = 0; i < n; ++i) {
      if (s[i] == '*') {
        rem[i] = true;
        for (int j = 0; j < 26; ++j) {
          if (!g[j].empty()) {
            rem[g[j].top()] = true;
            g[j].pop();
            break;
          }
        }
      } else {
        g[s[i] - 'a'].push(i);
      }
    }
    string ans;
    for (int i = 0; i < n; ++i) {
      if (!rem[i]) {
        ans.push_back(s[i]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def clearStars(self, s: str) -> str: g = defaultdict(list) n = len(s) rem = [False] * n for i, c in enumerate(s): if c == "*": rem[i] = True for a in ascii_lowercase: if g[a]: rem[g[a]. pop()] = True break else: g[c]. append(i) return "" . join(c for i, c in enumerate(s) if not rem[i])

```