Removing Stars From a String - Video Solutions

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.