LeetCode 2390 - Removing Stars From a String

LeetCode Problem 2390

Difficulty: 🟡 Medium
Topics: String, Stack, Simulation

Solution

Problem Understanding

This problem asks us to repeatedly process a string that contains lowercase English letters and star characters (*). Every star represents a removal operation. When we encounter a star, we must remove two things:

1. The star itself.
2. The closest non-star character immediately to its left.

We continue this process until all stars have been removed. The final result is the remaining string after every removal operation has been applied.

Another way to think about the problem is that every star behaves like a "delete previous character" instruction. If we scan the string from left to right, each normal character is added to the result, while each star removes the most recently added character.

The input consists of a single string s, whose length can be as large as 10^5. The string contains lowercase English letters and stars. The output is a new string representing what remains after all star operations have been completed.

The constraints are important here. Since the string length may reach 100,000, we need an efficient solution. Any approach that repeatedly rebuilds the string or scans backwards for every star may become too slow. A quadratic time solution would struggle on the upper bound.

Several edge cases are worth considering upfront. A string may contain many consecutive stars, meaning multiple previously added characters must be removed in sequence. The entire string may disappear, producing an empty result. A star can never appear without a removable character to its left, because the problem guarantees that every operation is valid. This guarantee simplifies the implementation because we do not need defensive checks for invalid removals.

Approaches

Brute Force Approach

A straightforward approach is to simulate the removals exactly as described. Every time we encounter a star, we search leftward to find the nearest non-star character, remove both the character and the star, and rebuild the string.

For example, with "leet**cod*e":

• Remove t and the first *
• Remove e and the second *
• Remove d and the final *

This approach is correct because it follows the problem statement literally. However, it is inefficient. Each star may require scanning backward through the string, and removing characters from strings repeatedly is expensive because strings are immutable in many languages.

In the worst case, such as a long string with many removals, this repeated scanning and reconstruction leads to O(n²) time complexity.

Optimal Approach, Stack Simulation

The key insight is that each star always removes the most recent valid character that has not already been removed.

This behavior naturally matches a stack. A stack follows the Last In, First Out principle:

• When we see a normal character, we push it onto the stack.
• When we see a star, we remove the most recently added character by popping from the stack.

At the end of the traversal, the stack contains exactly the characters that survive all removals. We simply join them into the final string.

This works efficiently because every character is pushed at most once and popped at most once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scans and rebuilds the string
Optimal	O(n)	O(n)	Uses a stack to efficiently simulate removals

Algorithm Walkthrough

1. Initialize an empty stack.

The stack will store characters that are currently part of the resulting string. We choose a stack because each star removes the most recently added valid character. 2. Traverse the string from left to right.

We process one character at a time so that we simulate the operations in their natural order. 3. If the current character is a letter, push it onto the stack.

This means the character is currently part of the surviving string unless removed later by a star. 4. If the current character is a star (*), pop the top character from the stack.

The top of the stack represents the closest non-star character to the left that has not already been removed. The problem guarantees that such a character always exists. 5. Continue until the entire string has been processed.

By this point, all removals have been simulated. 6. Join all characters in the stack into a single string.

The stack now contains the final remaining characters in the correct order.

Why it works

The algorithm maintains an important invariant: after processing the first i characters, the stack contains exactly the resulting string that would remain after applying all star removals within those i characters.

When we encounter a normal character, adding it to the stack matches appending it to the evolving string. When we encounter a star, removing the stack top matches removing the closest surviving non-star character to the left. Since every operation is simulated correctly and in order, the final stack must equal the unique final answer.

Python Solution

class Solution:
    def removeStars(self, s: str) -> str:
        stack: list[str] = []

        for char in s:
            if char == "*":
                stack.pop()
            else:
                stack.append(char)

        return "".join(stack)

The implementation follows the algorithm directly. We begin by creating an empty list called stack. In Python, a list works efficiently as a stack because append() and pop() from the end both run in constant time.

We iterate through every character in the input string. If the character is a star, we remove the most recently added character using pop(). Otherwise, we append the character to the stack.

Once the traversal is complete, the stack contains only the surviving characters in order. Since the stack is a list of individual characters, we use "".join(stack) to build the final string efficiently.

The implementation is concise because the problem guarantee ensures every star operation is valid, meaning pop() will never be called on an empty stack.

Go Solution

func removeStars(s string) string {
	stack := make([]byte, 0, len(s))

	for i := 0; i < len(s); i++ {
		if s[i] == '*' {
			stack = stack[:len(stack)-1]
		} else {
			stack = append(stack, s[i])
		}
	}

	return string(stack)
}

The Go implementation follows the same logic as the Python version but uses a byte slice as the stack. Since the input contains only lowercase English letters and *, using []byte is efficient and avoids unnecessary string operations.

Instead of pop(), Go removes the last element using slice truncation:

stack = stack[:len(stack)-1]

Appending characters uses append(), and the final byte slice is converted back into a string using string(stack).

Unlike Python, Go strings are immutable byte sequences, so using a mutable slice is the natural way to implement stack behavior efficiently.

Worked Examples

Example 1

Input: s = "leet**cod*e"

We process the string one character at a time.

Character	Action	Stack State
l	push	["l"]
e	push	["l", "e"]
e	push	["l", "e", "e"]
t	push	["l", "e", "e", "t"]
*	pop t	["l", "e", "e"]
*	pop e	["l", "e"]
c	push	["l", "e", "c"]
o	push	["l", "e", "c", "o"]
d	push	["l", "e", "c", "o", "d"]
*	pop d	["l", "e", "c", "o"]
e	push	["l", "e", "c", "o", "e"]

Final result:

"lecoe"

Example 2

Input: s = "erase*****"

Character	Action	Stack State
e	push	["e"]
r	push	["e", "r"]
a	push	["e", "r", "a"]
s	push	["e", "r", "a", "s"]
e	push	["e", "r", "a", "s", "e"]
*	pop e	["e", "r", "a", "s"]
*	pop s	["e", "r", "a"]
*	pop a	["e", "r"]
*	pop r	["e"]
*	pop e	[]

Final result:

""

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every character is processed once, and each character is pushed and popped at most once
Space	O(n)	In the worst case, the stack stores all characters

The time complexity is linear because we only traverse the string once. Although pop operations occur, each character can only be removed once, so the total amount of work remains proportional to n.

The space complexity is O(n) because, in the worst case where there are no stars, all characters remain in the stack.

Test Cases

solution = Solution()

assert solution.removeStars("leet**cod*e") == "lecoe"  # Provided example
assert solution.removeStars("erase*****") == ""  # Entire string removed

assert solution.removeStars("a*") == ""  # Smallest valid removal
assert solution.removeStars("abc") == "abc"  # No stars
assert solution.removeStars("abc***") == ""  # Remove everything
assert solution.removeStars("ab**c") == "c"  # Consecutive removals
assert solution.removeStars("abc*d*") == "ab"  # Mixed additions and removals
assert solution.removeStars("a*b*c*") == ""  # Alternating character and star
assert solution.removeStars("xyz**") == "x"  # Multiple stars at the end
assert solution.removeStars("abcdef***") == "abc"  # Partial removal
assert solution.removeStars("aa*b*c") == "ac"  # Duplicate letters
assert solution.removeStars("z" * 100000) == "z" * 100000  # Large input, no removals

Test	Why
"leet**cod*e"	Validates the provided example
"erase*****"	Confirms the entire string can disappear
"a*"	Tests smallest valid removal
"abc"	Verifies behavior when no stars exist
"abc***"	Ensures all characters can be removed
"ab**c"	Tests consecutive star removals
"abc*d*"	Validates mixed operations
"a*b*c*"	Tests alternating push and pop behavior
"xyz**"	Verifies stars near the end
"abcdef***"	Tests partial removal
"aa*b*c"	Ensures duplicate letters are handled correctly
Large input	Confirms scalability to constraint limits

Edge Cases

Entire String Gets Removed

An input like "erase*****" removes every character. A buggy implementation might incorrectly leave residual characters or fail when the stack becomes empty. Our implementation handles this naturally because each star removes exactly one character, and the final join operation correctly produces an empty string.

Consecutive Stars

Inputs such as "ab**c" contain multiple stars in a row. A naive implementation may accidentally remove the wrong character if it does not correctly track prior removals. The stack structure solves this cleanly because each pop() always removes the most recent surviving character.

No Stars Present

An input like "abcdef" contains no removal operations. Some implementations may overcomplicate the logic or accidentally modify the string. In our solution, every character is simply pushed onto the stack and returned unchanged.

Very Large Input

Since s.length can be as large as 100,000, inefficient string rebuilding can become a performance problem. A quadratic solution may time out on worst case inputs. Our stack-based approach processes each character once, making it efficient enough for the maximum constraint size.