Removing Stars From a String

medium string stack

Problem

A '*' character acts as a backspace: it deletes the closest non-star character to its left. Return the final string after every star has been processed. Use a stack: push letters, pop on stars.

Inputs = "fb*ar"

Output"far"

'*' deletes the preceding 'b'.

s (letters and *)

def remove_stars(s):
    out = []
    for c in s:
        if c == '*': out.pop()
        else: out.append(c)
    return "".join(out)

function removeStars(s) {
  const out = [];
  for (const c of s) {
    if (c === '*') out.pop();
    else out.push(c);
  }
  return out.join("");
}

class Solution {
    public String removeStars(String s) {
        StringBuilder out = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == '*') out.deleteCharAt(out.length() - 1);
            else out.append(c);
        }
        return out.toString();
    }
}

string removeStars(string s) {
    string out = "";
    for (char c : s) {
        if (c == '*') out.pop_back();
        else out += c;
    }
    return out;
}

Explanation

Each * behaves like a backspace that erases the nearest letter to its left. The natural tool for "undo the most recent thing" is a stack, where the most recently added letter is always on top.

The whole algorithm is two rules applied as we scan left to right: if the character is a normal letter, push it onto the stack; if it is a *, pop the top letter off (that letter just got deleted by the backspace).

This works because the top of the stack is always exactly the "closest non-star character to the left" that a star would target. Popping it removes precisely the right letter, and the letter beneath becomes the new candidate for any future star.

Example: s = "fb*ar". Push f, push b → stack [f, b]. The * pops b → [f]. Then push a, push r → [f, a, r]. Joining gives "far".

At the end, the letters remaining on the stack, read in order, form the final string.

Time: O(n) Space: O(n)