# Removing Stars From a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/removing-stars-from-a-string)
Canonical: https://scaleengineer.com/dsa/problems/removing-stars-from-a-string
**Data structures:** String, Stack
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
You are given a string `s`, which contains stars `*`.

In one operation, you can:

* Choose a star in `s`.
* Remove the closest **non-star** character to its **left**, as well as remove the star itself.

Return _the string after **all** stars have been removed_.

**Note:**

* The input will be generated such that the operation is always possible.
* It can be shown that the resulting string will always be unique.

**Example 1:**

**Input:** s = "leet**cod*e"
**Output:** "lecoe"
**Explanation:** Performing the removals from left to right:
- The closest character to the 1st star is 't' in "lee**t****cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "le**e***cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "leco**d***e". s becomes "lecoe".
There are no more stars, so we return "lecoe".

**Example 2:**

**Input:** s = "erase*****"
**Output:** ""
**Explanation:** The entire string is removed, so we return an empty string.

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of lowercase English letters and stars `*`.
* The operation above can be performed on `s`.

# Approaches
## Stack-Based Simulation
This approach correctly identifies the problem's Last-In, First-Out (LIFO) nature. When we encounter a character, we add it to a temporary sequence. When we encounter a star, we remove the last character added. A stack is the perfect data structure for this behavior.
**Time:** O(N), where N is the length of the string. We iterate through the string once (O(N)). Each character is pushed and popped at most once (O(1) per operation). Building the final string from the stack also takes O(K) time, where K is the length of the result (K <= N). · **Space:** O(N), where N is the length of the string. In the worst-case scenario (a string with no stars), the stack will store all N characters.
**Pros:** Intuitive and directly models the LIFO process.; Clean and easy to understand.
**Cons:** Uses the `Stack` class which might have slightly more overhead than a more direct implementation like `StringBuilder` or an array.
### Explanation
The core idea is to process the string from left to right. We use a stack to keep track of the non-star characters encountered so far.

*   When we see a non-star character, we push it onto the stack.
*   When we see a star `'*'`, it signifies the removal of the most recently added non-star character. This corresponds to popping an element from the stack.

After iterating through the entire string, the characters remaining in the stack, when read from bottom to top, form the final string.

```java
import java.util.Stack;

class Solution {
    public String removeStars(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '*') {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(c);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char c : stack) { // Iterating through stack in Java is from bottom to top
            sb.append(c);
        }
        return sb.toString();
    }
}
```
### Algorithm
*   Initialize an empty `Stack<Character>`.
*   Iterate through each character `c` of the input string `s`.
*   If `c` is a star `'*'`: 
    *   Pop an element from the stack. The problem guarantees the stack will not be empty.
*   If `c` is a letter:
    *   Push `c` onto the stack.
*   After the loop, the stack contains the characters of the resulting string.
*   To construct the final string, iterate through the stack (which in Java iterates from bottom to top) and append each character to a `StringBuilder`.
*   Return the string from the `StringBuilder`.

## Two Pointers / StringBuilder Approach
This is an optimized approach that simulates a stack using a more direct and often faster data structure like a `StringBuilder`. Instead of using the `Stack` class, we build the result string directly, which can be more performant.
**Time:** O(N), where N is the length of the string. We perform a single pass over the string. `StringBuilder.append()` is amortized O(1), and `StringBuilder.deleteCharAt(length - 1)` is O(1). · **Space:** O(N). The `StringBuilder` can grow up to size N in the worst case (no stars). This space is used to construct the output string.
**Pros:** Highly efficient, often faster in practice than using the `Stack` class due to less overhead.; Code is very concise and readable.
**Cons:** The LIFO pattern might be slightly less explicit than when using a `Stack` object, but it's a very common and idiomatic pattern.
### Explanation
This approach uses a `StringBuilder` to directly build the final string, effectively simulating a stack. This avoids the overhead of the `Stack` class and is a common and efficient pattern in Java for string manipulation problems. The end of the `StringBuilder` acts as the top of the stack. This method is conceptually identical to a two-pointer approach where the `StringBuilder`'s length acts as the `write_ptr`, and the loop variable acts as the `read_ptr`.

```java
class Solution {
    public String removeStars(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == '*') {
                // The problem guarantees this operation is always possible,
                // so we don't need to check if sb is empty.
                sb.deleteCharAt(sb.length() - 1);
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
```
### Algorithm
*   Initialize an empty `StringBuilder` which will hold the result.
*   Iterate through each character `c` of the input string `s`.
*   If `c` is a star `'*'`: 
    *   Remove the last character from the `StringBuilder`. The problem guarantees the `StringBuilder` will not be empty.
*   If `c` is a letter:
    *   Append `c` to the `StringBuilder`.
*   After iterating through all characters, the `StringBuilder` contains the final, correct string.
*   Convert the `StringBuilder` to a string and return it.

# Solutions
### CPP

```cpp
class Solution {
public:
  string removeStars(string s) {
    string ans;
    for (char c : s) {
      if (c == '*') {
        ans.pop_back();
      } else {
        ans.push_back(c);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def removeStars(self, s: str) -> str: ans = [] for c in s: if c == '*': ans . pop() else: ans . append(c) return '' . join(ans)

```

### Java

```java
class Solution {
public
  String removeStars(String s) {
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == '*') {
        ans.deleteCharAt(ans.length() - 1);
      } else {
        ans.append(s.charAt(i));
      }
    }
    return ans.toString();
  }
}

```