Removing Stars From a String
Understanding the Problem
A * behaves like a backspace key in a text editor. It deletes the most recent non-star character to its left, and the string is processed left to right.
Since each star removes the closest surviving character to its left, the order of removals is fully determined. In "ab*", the * removes 'b' and leaves "a". In "ab**", the first * removes 'b' and the second removes 'a', leaving an empty string. A star can also cancel a character that an earlier star already exposed, so removals can chain backward through the string.
This "add a character, then undo the most recent addition" behavior maps directly onto a stack: letters get pushed, and stars pop the top.
Key Constraints:
1 <= s.length <= 10^5→ With up to 100,000 characters, an O(n^2) approach that repeatedly shifts the string can reach about 10^10 operations, too slow under typical limits. A single-pass O(n) solution is the target.sconsists of lowercase English letters and stars*→ The only distinction that matters is letter versus star.- The operation can always be applied → Every star has a non-star character to its left, so we never have to handle a star with nothing to remove.
Approach 1: Brute Force Simulation
Intuition
Simulate the operation literally: find a star, remove it along with the character to its left, then continue scanning. This mirrors the problem statement step for step.
The cost shows up in the removals. Deleting a character from the middle of a string or list shifts every element after it, and a fresh scan has to resume near the deletion point because positions changed. With many stars, that shifting work dominates.
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.
The repeated shifting is the bottleneck. The next approach builds the result in a single pass instead, touching each character exactly once.
Approach 2: Stack (StringBuilder)
Intuition
Build the result in a single pass using a stack. As we scan left to right, a letter gets pushed onto the stack, and a star pops the top element. The pop discards the most recent surviving letter, which is the closest non-star to the left of that star.
After the scan, the stack holds the answer in order. Because every operation only adds to or removes from the end, a StringBuilder (or list) serves as the stack, with no shifting or rescanning.
The pop is always safe. The problem guarantees a non-star character to the left of every star, so any surviving letter to a star's left is still on the stack, meaning the stack is non-empty when we reach a star.
The pop also removes the correct character. The top of the stack is the most recently pushed surviving letter, which is the nearest non-star to the left of the current star. Letters that no star removes stay on the stack in their original order, so the final stack reads left to right as the answer.
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 runs in O(n) time but allocates a separate structure for O(n) extra space. The next approach removes that allocation by treating the input array itself as the stack, using a single write pointer.
Approach 3: In-Place with Write Pointer
Intuition
Reuse the character array as the stack. A write pointer marks where the next surviving character belongs, and the loop variable acts as the read pointer scanning left to right.
For a letter, store it at index write and advance write. For a *, decrement write, which logically removes the last stored character so the next letter overwrites it. At the end, indices 0 through write - 1 hold the result.
The invariant write <= read holds throughout. The read pointer advances by one every iteration, while write either advances by one (on a letter) or decreases (on a star), so it can never move ahead of read. We therefore only overwrite positions at or before the current read index, never a character still waiting to be read.
The prefix arr[0..write) is the same stack from the previous approach, stored in the array instead of a separate buffer.
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). A single pass over the string, with O(1) work per character.
- Space Complexity: O(n) for the mutable character array in languages with immutable strings (Java, Python, C#, Go, Rust, JavaScript). In C++, the string is mutable and we overwrite it directly, so the extra space beyond the output is O(1).