Removing Stars From a String

Q: What is the time complexity of Removing Stars From a String?

O(n). Each character is processed exactly once. Push and pop operations on the stack are O(1), so the total time is linear in the length of the string.

Q: What pattern does Removing Stars From a String use?

The Pattern: Stacks (Last-In-First-Out Removal) The Heuristic: When a problem requires removing the most recent element before a certain marker (like a star), a stack efficiently models this by pushing elements and popping upon encountering the marker, enabling linear-time processing of paired removals.

Medium Stacks

Problem

Given a string s containing lowercase English letters and '*' characters, return the string after removing all stars and the closest non-star character to the left of each star.

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters and '*' characters.
Every star has a non-star character to its left.

Example

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

Output: "lecoe"

The algorithm processes the string from left to right. When it encounters a letter, it adds it to a stack. When it encounters a '*', it removes the most recent letter from the stack. For the input "leet**cod*e": - Add 'l', 'e', 'e', 't' to the stack. - Encounter '*', pop 't'. - Encounter '*', pop 'e'. - Add 'c', 'o', 'd' to the stack. - Encounter '*', pop 'd'. - Add 'e' to the stack. The final stack is ['l', 'e', 'c', 'o', 'e'], which joins to "lecoe".

Approach

Straightforward Solution

A naive approach would repeatedly scan the string to find stars and remove the preceding character, which is inefficient (O(n^2)) due to repeated string modifications.

Core Observation

Each star in the string removes the closest preceding non-star character. This naturally suggests a last-in-first-out structure to track characters, making a stack the ideal data structure.

Path to Optimal

Preview

Recognizing the problem as a sequence of paired removals, a stack can efficiently track characters. Each letter is pushed onto the stack, and each star triggers a pop, effectively removing the closest preceding letter…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the string once, pushing letters onto a stack and popping when a star is encountered. After processing, join the stack contents to form the resulting string…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each character is processed exactly once. Push and pop operations on the stack are O(1), so the total time is linear in the length of the string.

Space

O(n)

In the worst case, the stack stores all non-star characters, which can be up to the length of the input string. This auxiliary space is necessary to reconstruct the final string.

Pattern Spotlight

Stacks (Last-In-First-Out Removal)

When a problem requires removing the most recent element before a certain marker (like a star), a stack efficiently models this by pushing elements and popping upon encountering the marker, enabling linear-time processing of paired removals.

Solution

Python

1class Solution:
  def removeStars(self, s: str) -> str:
      stack = []
4
      for char in s:
          if char == "*":
              stack.pop()
          else:
              stack.append(char)
10
      return "".join(stack)

Step-by-Step Solution

Use a Stack to Track Characters and Remove on Star Encounter

3stack = []
5for char in s:
6    if char == "*":
7        stack.pop()
8    else:
9        stack.append(char)

Objective

To process the string in one pass, pushing letters onto a stack and popping the top element when a star is encountered.

Key Insight

The stack maintains the current valid characters of the string as it is being processed. When a star appears, the closest preceding character is always at the top of the stack, so popping it simulates the removal. This approach avoids costly string slicing or repeated scanning, achieving linear time complexity.

Interview Quick-Check

Core Logic

Push letters onto the stack and pop the top element when a star is encountered, ensuring the closest preceding character is removed.

State & Boundaries

The stack always contains only valid characters that have not been removed by stars.

Common Pitfalls & Bugs

Failing to pop the stack on encountering a star or incorrectly handling empty stack cases can cause errors.

Construct the Result String from the Stack

To join the characters remaining in the stack into the final processed string.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 7 Critical

stack.pop()

Remove the most recent character from the stack when a star is encountered.

Popping the stack simulates removing the closest preceding character to the star, leveraging the stack's last-in-first-out property to maintain correctness and efficiency.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why is a stack the appropriate data structure for this problem instead of a queue or direct string manipulation?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Removing Stars From a String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Removing Stars From a String drill

or drill a free problem

1	`class Solution:`
2	`def removeStars(self, s: str) -> str:`
3	`stack = []`
4
5	`for char in s:`
6	`if char == "*":`
7	`stack.pop()`
8	`else:`
9	`stack.append(char)`
10
11	`return "".join(stack)`

3	`stack = []`
5	`for char in s:`
6	`if char == "*":`
7	`stack.pop()`
8	`else:`
9	`stack.append(char)`