Removing Stars From a String

Med

#2175Time: 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.1 company

Data structures

String Stack

Companies

IBM

Prompt

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 "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*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 <= 10⁵
s consists of lowercase English letters and stars *.
The operation above can be performed on s.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.Stack;2 3class Solution {4    public String removeStars(String s) {5        Stack<Character> stack = new Stack<>();6        for (char c : s.toCharArray()) {7            if (c == '*') {8                if (!stack.isEmpty()) {9                    stack.pop();10                }11            } else {12                stack.push(c);13            }14        }15 16        StringBuilder sb = new StringBuilder();17        for (char c : stack) { // Iterating through stack in Java is from bottom to top18            sb.append(c);19        }20        return sb.toString();21    }22}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public String removeStars(String s) {3        StringBuilder sb = new StringBuilder();4        for (char c : s.toCharArray()) {5            if (c == '*') {6                // The problem guarantees this operation is always possible,7                // so we don't need to check if sb is empty.8                sb.deleteCharAt(sb.length() - 1);9            } else {10                sb.append(c);11            }12        }13        return sb.toString();14    }15}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public:3  string removeStars(string s) {4    string ans;5    for (char c : s) {6      if (c == '*') {7        ans.pop_back();8      } else {9        ans.push_back(c);10      }11    }12    return ans;13  }14};

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

1class Solution {2public3  String removeStars(String s) {4    StringBuilder ans = new StringBuilder();5    for (int i = 0; i < s.length(); ++i) {6      if (s.charAt(i) == '*') {7        ans.deleteCharAt(ans.length() - 1);8      } else {9        ans.append(s.charAt(i));10      }11    }12    return ans.toString();13  }14}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem