Removing Stars From a String
Last Updated: April 1, 2026
Understanding the Problem
Think of typing in a text editor where * acts like a backspace key. Every time you encounter a *, it deletes the most recent non-star character you typed. The string is processed left to right, and each star removes exactly one character to its left.
The key insight is that a star always removes the closest non-star character to its left. So if you have "ab*", the * removes 'b' and you are left with "a". If you have "ab**", the first * removes 'b' and the second * removes 'a', leaving an empty string.
This "type a character, then potentially delete it" pattern is exactly what a stack handles well. Characters go on the stack, and stars pop them off.
Key Constraints:
1 <= s.length <= 10^5→ With up to 100,000 characters, we need an O(n) or O(n log n) approach. An O(n^2) approach (repeatedly scanning and removing) could hit 10^10 operations in the worst case, which is too slow.sconsists of lowercase English letters and stars*→ Simple character set, no special handling needed beyond distinguishing stars from letters.- The operation can always be applied → Every star is guaranteed to have a non-star character to its left. We do not need to handle the case where a star has nothing to remove.
Approach 1: Brute Force Simulation
Intuition
The most straightforward way to handle this: find a star, remove it along with the character to its left, and repeat. Each time you remove a star, you scan the string again to find the next one. This directly simulates the operation described in the problem.
It is simple to understand but inefficient. Every removal operation requires rebuilding or shifting part of the string, and you have to scan from the beginning each time because earlier removals might shift positions.
Algorithm
- Convert the string to a mutable list of characters.
- Scan the list from left to right looking for a
*. - When you find a
*at indexi: - Remove the
*at indexi. - Remove the character at index
i - 1(the closest non-star to its left). - Restart the scan from the adjusted position.
- When a full scan finds no stars, convert the list back to a string and return it.
Example Walkthrough
Code
- Time Complexity: O(n^2). In the worst case, stars are clustered at the end. Each removal shifts elements in the list, costing O(n) per removal. With up to n/2 stars, that gives O(n^2) total.
- Space Complexity: O(n). We store a mutable copy of the input string.
Every time we encounter a star, we remove two characters from the list, which shifts all subsequent elements. What if instead of modifying the string with costly removals, we built the result incrementally, processing each character just once?
Approach 2: Stack (StringBuilder)
Intuition
Instead of repeatedly modifying the string, we can build the result in a single pass. Think of it like typing on a keyboard. As you scan left to right: if the character is a letter, type it (push onto a stack). If the character is a *, press backspace (pop the most recent letter from the stack).
After processing every character, whatever remains in the stack is the final string. Since we only need to add to the end and remove from the end, a StringBuilder (or list) works perfectly as our "stack." No shifting, no rescanning.
The problem guarantees that every star has a non-star character to its left. That means whenever we encounter a *, the stack is guaranteed to be non-empty. So we can always safely pop.
The stack preserves the left-to-right order of surviving characters. Characters that were never removed by a star stay in the order they appeared. And because each star removes the most recent character (the one on top of the stack), the LIFO behavior of the stack perfectly matches the "closest non-star to its left" requirement.
Algorithm
- Initialize an empty StringBuilder (acting as a stack).
- Iterate through each character in
s: - If the character is
*, remove the last character from the StringBuilder (pop). - Otherwise, append the character to the StringBuilder (push).
- Return the StringBuilder as a string.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the string once. Each character is either pushed or triggers a pop, both O(1) operations.
- Space Complexity: O(n). The stack can hold up to n characters in the worst case (when there are no stars).
The stack approach is already O(n) time, but we are using O(n) extra space for a separate data structure. What if we could use the input array itself as the stack, writing results in-place with a pointer?
Approach 3: In-Place with Write Pointer
Intuition
Instead of maintaining a separate stack, we can use a write pointer on a character array. As we scan left to right, we overwrite the array in place. A pointer write tracks where the next surviving character should go.
When we see a letter, write it at position write and advance the pointer. When we see a *, move the pointer back by one, effectively "deleting" the last written character. At the end, everything from index 0 to write - 1 is the result.
The write pointer never overtakes the read pointer (the loop variable). At any point, write <= read because stars only decrease write while the read pointer always moves forward. So we never overwrite a character we have not yet read.
This is the same logic as the stack approach, just without allocating a separate data structure. The prefix of the array up to write is the implicit stack at all times.
Algorithm
- Convert the string to a character array.
- Initialize a write pointer
write = 0. - Iterate through each character:
- If the character is
*, decrementwriteby 1. - Otherwise, write the character at
arr[write]and incrementwrite. - Return the substring from index 0 to
write.
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the string. Each character involves O(1) work.
- Space Complexity: O(n). We convert the string to a character array. In C++, where strings are mutable, this is truly O(1) extra space since we modify the string in place.