Removing Stars From a String

MediumStack · String🧩 Stack LeetCode #2390 ↗Updated Oct 30, 2026

Problem

A string s mixes lowercase letters and '*' characters. Each star acts like a backspace: it erases itself together with the closest not-yet-erased letter on its left. Apply this for every star and return what remains. The input guarantees every star has a letter available to erase, and the result is unique.

Inputs = "leet**cod*e"Output"lecoe"

Inputs = "erase*****"Output""

Inputs = "ab*c"Output"ac"

1 ≤ s.length ≤ 10⁵ · s has lowercase letters and '*' · the operation is always possible

Try it yourself

Java

class Solution {
    public String removeStars(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A star always removes the most recently kept letter — last in, first out. So the kept letters form a stack: letters push, stars pop.

PatternStack

Instinct Things resolve in reverse order of arrival (brackets, adjacent pairs, nested expressions) - push now, pop when its partner shows up.

Memory hack Last in, first out - like a pile of plates, you only ever touch the one on top; every closer pops its opener.

Open the Stack guide →

Approaches

Brute ForceSimulate Each Star with Deletions

Time O(n²)Space O(n)

Find the leftmost star; the character just before it is the nearest kept letter (anything earlier is a letter, since earlier stars are already gone). Delete both and repeat. Every deletion shifts the tail of the buffer, so many stars make it quadratic.

Java

public String removeStars(String s) {
    StringBuilder sb = new StringBuilder(s);
    int i = 0;
    while (i < sb.length()) {
        if (sb.charAt(i) == '*') {
            sb.delete(i - 1, i + 1); // the star and its left letter, O(n) shift
            i--;                      // continue right where the letter was
        } else {
            i++;
        }
    }
    return sb.toString();
}

Direct translation of the rules, but O(n²) for star-heavy inputs.

BetterExplicit Stack

Time O(n)Space O(n)

Scan once. Push each letter; on a star pop the top, which is exactly the nearest surviving letter to the left. The stack, read from bottom to top, is the answer.

Java

public String removeStars(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '*') stack.pop(); // guaranteed non-empty
        else stack.push(c);
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pollLast()); // bottom first
    return sb.toString();
}

Linear, but uses a boxed Deque plus a rebuild step.

OptimalWrite Pointer (char[] as Stack)

Time O(n)Space O(n)

Let the array prefix a[0..w-1] be the stack. A letter is written at w and w grows; a star just decrements w. w never exceeds the read index, so overwriting is safe. Return the first w characters.

Java

public String removeStars(String s) {
    char[] a = s.toCharArray();
    int w = 0; // size of the kept prefix
    for (int r = 0; r < a.length; r++) {
        if (a[r] == '*') w--;  // erase the last kept letter
        else a[w++] = a[r];
    }
    return new String(a, 0, w);
}

Dry run"ab*c*d"

w write (stack size)r read changed

r=1
a

b
r
*
w
c

*

d

kept "ab"
r=2
a

b
w
*
r
c

*

d

star → w=1
r=3
a

c

*
w
c
r
*

d

write c, w=2
r=4
a

c
w
*

c

*
r
d

star → w=1
r=5
a

d

*
w
c

*

d
r
return "ad" ✔

Single pass with the smallest constant factor — only the output buffer.

Pro tip

Alternative: scan from the right keeping a count of pending stars and skip that many letters — same O(n), then reverse the output.

At a glance

Level	Approach	Time	Space
Brute Force	Simulate Each Star with Deletions	`O(n²)`	`O(n)`
Better	Explicit Stack	`O(n)`	`O(n)`
Optimal	Write Pointer (char[] as Stack)	`O(n)`	`O(n)`

Common pitfalls

Erasing the nearest letter to the right of the star instead of the left.
Building the result with s.substring/string concatenation in a loop — O(n²).
Reading the Deque top-first — produces the answer reversed.

Interview tips

Spot the backspace analogy right away — it screams “stack”.
Note the guarantee means no empty-stack check is required (mention it anyway).
Finish with the in-place write pointer to show constant-factor awareness.

Pattern

Stack / write-pointer simulation → backspace-style edits that undo the most recent kept item.

My notes saved in this browser