Removing Stars From a String
MedPrompt
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 <= 105sconsists 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
cof the input strings. - If
cis a star'*':- Pop an element from the stack. The problem guarantees the stack will not be empty.
- If
cis a letter:- Push
conto the stack.
- Push
- 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.
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(); }}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
Stackclass which might have slightly more overhead than a more direct implementation likeStringBuilderor an array.
Solutions
Solution
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; }};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.