You are given a string s, which contains stars *.
In one operation, you can:
s.Return the string after all stars have been removed.
Note:
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 <= 105s consists of lowercase English letters and stars *.s.Problem Overview: You are given a string where the character * represents a deletion operation. Each star removes the closest non-deleted character to its left along with the star itself. After processing the entire string, return the final string that remains.
This problem is essentially a simulation of deletions while scanning the string. The key challenge is efficiently identifying and removing the most recent valid character when a star appears. Because deletions always target the closest character to the left, the problem naturally maps to a Last-In-First-Out structure.
Approach 1: Stack-based Simulation (O(n) time, O(n) space)
The most direct solution uses a stack to simulate the removal process. Iterate through the string character by character. When you see a regular character, push it onto the stack. When you encounter *, pop the top character from the stack because that represents the closest undeleted character to the left. This works because the most recently added character is exactly the one that should be removed.
After processing all characters, the stack contains the remaining characters in order. Convert the stack back into a string to produce the result. Each character is pushed and popped at most once, so the total time complexity is O(n). The stack can grow up to the length of the string, giving O(n) space complexity. This approach is intuitive and commonly used for problems involving undo-like operations or nested processing in string manipulation.
Approach 2: Two-pointer Technique (O(n) time, O(n) space)
A more space-efficient simulation can be built using the two-pointer technique and processing the string from right to left. The key observation: when you see a star, it will delete one valid character to its left. Instead of immediately removing characters, track how many characters should be skipped.
Traverse the string from the end while maintaining a counter of pending deletions. When you see *, increment the counter. When you see a normal character and the counter is greater than zero, skip the character and decrement the counter because it gets removed by a star. If the counter is zero, keep the character. Append kept characters to a result buffer and reverse it at the end.
This approach still runs in O(n) time because each character is processed once. The extra space for the output string is O(n). It avoids the explicit stack structure and instead relies on pointer traversal and deletion counting, which can feel cleaner in languages where stack operations add overhead.
Recommended for interviews: The stack-based approach is the one most interviewers expect because the deletion rule directly matches stack behavior. Implementing it quickly shows strong intuition for LIFO problems and string simulation. The two-pointer version demonstrates deeper insight into optimizing simulations by reversing traversal and tracking pending operations.
This approach utilizes a stack data structure to handle the character removals efficiently. As we iterate through the string, whenever a star (*) is encountered, we pop from the stack, effectively removing the last non-star character added. This allows us to handle both the star and its preceding non-star character in O(1) time.
The C implementation uses a character array as a stack to store non-star characters. We increment the top index when adding a character and decrement it when encountering a star, which effectively removes the most recent non-star character.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for the stack to hold characters.
This alternative method involves using a simple two-pointer technique where we iterate through the string and build the result in place. We treat the string as a writable array and maintain a 'write' index that tells us where to place the next character. When we encounter a star, we just need to move the 'write' index back to overwrite the previous character.
This C implementation makes use of two indices: read, which traverses the string, and write, which indicates where to write the next character.
Time Complexity: O(n)
Space Complexity: O(1), since operations are done in-place.
We can use a stack to simulate the operation process. Traverse the string s, and if the current character is not an asterisk, push it onto the stack; if the current character is an asterisk, pop the top element from the stack.
Finally, concatenate the elements in the stack into a string and return it.
The time complexity is O(n), where n is the length of the string s. Ignoring the space consumption of the answer string, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Stack-based Approach | Time Complexity: O(n), where n is the length of the string. |
| Two-pointer Technique | Time Complexity: O(n) |
| Stack Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Simulation | O(n) | O(n) | Best general solution. Clear mapping between '*' and stack pop operations. |
| Two-pointer Technique (right-to-left) | O(n) | O(n) | Useful when simulating deletions by counting operations instead of storing a stack. |
Removing Stars From a String - Leetcode 2390 - Python • NeetCodeIO • 46,430 views views
Watch 9 more video solutions →Practice Removing Stars From a String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor