Removing Stars from String LeetCode 2390

LeetCode 2390 — Removing Stars from a String — gives you a string containing lowercase letters and star characters. Each star removes the closest non-star character immediately to its left. After processing all stars, you return the remaining string with no stars in it. The problem guarantees that every star always has at least one non-star character to its left, so you never need to handle an invalid deletion.

The key insight is that stars act as a backspace key on whatever has been built so far. A star does not remove the character at a fixed offset — it removes the most recently added character that has not already been deleted by a previous star. This "most recently added" property is the hallmark of a stack (Last-In, First-Out).

The problem is solvable in a single left-to-right pass with no look-ahead. The result is always deterministic because the order of deletions is fully determined by the left-to-right traversal order.

The stack simulation iterates the string left to right one character at a time. For each character, apply a simple rule: if the character is not a star, push it onto the stack; if the character is a star, pop the top element from the stack. After processing all characters, join the stack into a string and return it.

Pushing a non-star character records that character as part of the current "typed" result. Popping on a star undoes the most recent addition — exactly the semantics of the nearest-left-non-star deletion rule. Because the stack always holds the characters that have survived all deletions so far, joining it at the end directly produces the answer.

This approach handles every edge case automatically. Multiple consecutive stars each pop once, removing two characters from the stack. Stars at the beginning of the string are impossible (guaranteed valid input). A string with no stars at all simply fills the stack with every character and joins to the original string.

A stack is the ideal data structure here because the deletion rule is LIFO: a star always removes the most recently added surviving character, not any arbitrary character. This is the defining property of a stack. Stack pop gives you the most recently pushed item in O(1) time without searching.

If you tried to solve this with an index into the original string, you would need to track which characters have been deleted and skip over them when looking left for the next surviving character — adding complexity. The stack eliminates that bookkeeping entirely: whatever is on top is always the nearest surviving character to the left.

The stack approach also makes the algorithm's correctness trivially obvious. After each push or pop, the stack invariant is: "the stack contains exactly the surviving characters from the portion of the string processed so far, in original left-to-right order." No additional reasoning is needed.

LeetCode 844 — Backspace String Compare — uses the exact same core mechanic: a hash "#" character acts as a backspace, deleting the previous character. The difference is that LeetCode 844 asks you to compare two processed strings for equality, while LeetCode 2390 asks you to return the processed string. The stack template that solves 2390 directly solves 844 as well — just run it on both input strings and compare the results.

Recognizing this family of problems — "character + delete signal" processed left to right — is a valuable pattern to internalize. Any time a problem describes a character that removes or cancels the character before it, reach for a stack. The delete signal (star, hash, or another marker) always maps to a pop, and every other character maps to a push.

Both problems are O(n) time and O(n) space. LeetCode 844 has a follow-up asking for O(1) space using two pointers scanning right to left, but that optimization applies to the comparison version and not to 2390 which must reconstruct the full output string.

Trace through "leet**cod*e" step by step. The string has 11 characters: l, e, e, t, *, *, c, o, d, *, e. Start with an empty stack [].

Process l → push → [l]. Process e → push → [l, e]. Process e → push → [l, e, e]. Process t → push → [l, e, e, t]. Process * → pop t → [l, e, e]. Process * → pop e → [l, e]. Process c → push → [l, e, c]. Process o → push → [l, e, c, o]. Process d → push → [l, e, c, o, d]. Process * → pop d → [l, e, c, o]. Process e → push → [l, e, c, o, e].

Join the stack: "lecoe". This is the correct answer. Notice that the two consecutive stars at positions 4-5 removed t then e (the two most recently pushed characters), and the star at position 9 removed d immediately after it was pushed. The stack cleanly handles all three deletions without any index arithmetic.

Python implementation: use a list as the stack. stack = []; for ch in s: if ch != "*": stack.append(ch); else: stack.pop(); return "".join(stack). Time complexity: O(n) — each character is pushed at most once and popped at most once. Space complexity: O(n) for the stack. A Python one-liner using functools.reduce is also possible — reduce(lambda acc, ch: acc[:-1] if ch == "*" else acc + ch, s, "") — but this builds intermediate strings and is O(n^2) in the worst case due to string concatenation; avoid it for large inputs.

Java implementation: use a StringBuilder as a stack surrogate. StringBuilder sb = new StringBuilder(); for (char ch : s.toCharArray()) { if (ch != '*') { sb.append(ch); } else { sb.deleteCharAt(sb.length() - 1); } } return sb.toString(). StringBuilder.deleteCharAt operates on an internal char array, making pop O(1) amortized. Return sb.toString() for the final result. Alternatively, use a Deque<Character> as an explicit stack and collect the result in order.

Both implementations are single-pass O(n) solutions. The Python list and the Java StringBuilder both support O(1) amortized append and O(1) remove-from-end, making them equivalent in performance. The key is to avoid any solution that builds the result using string concatenation in a loop, which degrades to O(n^2).

Decode String — LeetCode 394 — uses a stack to handle nested bracket-based repetition: push context on "[" and pop to expand on "]". Like 2390, the stack tracks what has been built so far, but here the stack holds (string, count) pairs rather than individual characters. Both problems share the "maintain a running result on a stack, modify it based on a special character" structure.

Valid Parentheses — LeetCode 20 — is the simplest stack string problem: push opening brackets and pop on closing ones, checking that each closing bracket matches the top of the stack. Asteroid Collision — LeetCode 735 — involves integers where negative values destroy positive ones to their left, structurally identical to the star-deletion pattern but with a comparison step on each potential collision.

Together, Removing Stars, Backspace String Compare, Valid Parentheses, Asteroid Collision, and Decode String form the stack string processing family. Each one uses a stack to simulate a sequential build-and-undo or build-and-match process. Mastering the template — push on regular input, pop on special signals, report the stack at the end — covers all of them.