Skip to main content

2390. Removing Stars From a String

medium

Each star removes the closest non-star to its left. The naive simulation is O(n^2) string concatenation — the stack reduces it to a single linear sweep.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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, and remove the star itself. Return the string after all stars have been removed. The operation is performed in some order so that all stars are eventually removed. The answer is guaranteed to be unique.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters and stars *.
  • The operation above can be performed on s.

Examples

Example 1

Input
s = "leet**cod*e"
Output
"lecoe"

Explanation: Process left to right: 'l','e' on stack; '*' pops 'e'; '*' pops 'e' (stack=['l']); push 'c','o','d'; '*' pops 'd'; push 'e'. Final: 'lecoe'.

Example 2

Input
s = "erase*****"
Output
""

Explanation: Five stars pop the five preceding letters, leaving an empty string.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Naive simulation: each star scans backward for the previous non-star, then slices the string. O(n^2) and terrible on long inputs.

Hint 2

Observation: 'remove the closest non-star to my left' is exactly 'pop the top of a stack'.

Hint 3

Scan once left to right. Push every letter onto a stack; when you see a star, pop instead of pushing.

Hint 4

Join the stack at the end. O(n) time, O(n) space — same as the output size.

Solution approach

Reveal approach

Single pass with a stack (or a mutable list used as a stack). Walk the string left to right. If the current character is a letter, append it. If it's a star, pop the last appended character. After the scan, join the stack and return. Why this works: stars must annihilate the latest unmatched letter (the 'closest non-star to its left'), and a stack naturally tracks 'latest unmatched' in O(1) per op. Each character is pushed at most once and popped at most once, giving O(n) total time and O(n) space (output bound). In languages where string mutation is expensive (Python, Java), append to a list / StringBuilder and join at the end — never rebuild the string mid-loop.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Removing Stars From a String and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →