# LC 3170. Lexicographically Minimum String After Removing Stars

### [Problem link](https://leetcode.com/problems/lexicographically-minimum-string-after-removing-stars/)

###### tags: `leedcode` `medium` `c++` `Greedy`

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

While there is a <code>'*'</code>, do the following operation:

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

Return the <span data-keyword="lexicographically-smaller-string">lexicographically smallest resulting string after removing all <code>'*'</code> characters.

**Example 1:**

<div class="example-block">
Input: <span class="example-io">s = "aaba*"

Output: <span class="example-io">"aab"

Explanation:

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

**Example 2:**

<div class="example-block">
Input: <span class="example-io">s = "abc"

Output: <span class="example-io">"abc"

Explanation:

There is no <code>'*'</code> in the string.<!-- notionvc: ff07e34f-b1d6-41fb-9f83-5d0ba3c1ecde -->

**Constraints:**

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

## Solution 1
#### C++

class Solution {
public:
    string clearStars(string s) {
        vector<int> st[26];
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '*') {
                for (vector<int>& s: st) {
                    if (!s.empty()) {
                        s.pop_back();
                        break;
                    }
                }
            } else {
                st[s[i] - 'a'].push_back(i);
            }
        }

        string tmp(s.size(), ' ');
        for (int i = 0; i < 26; i++) {
            for (int& t: st[i]) {
                tmp[t] = 'a' + i;
            }
        }

        string res;
        for (char& c: tmp) {
            if (c != ' ') {
                res += c;
            }
        }

        return res;
    }
};

>### Complexity
>n = s.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
x