#2390 - Removing Stars From a String

MediumStack

Given a string s containing lowercase letters and stars *, in one operation a star removes the closest non-star character to its left as well as itself. Return the string after all stars have been processed. The input is guaranteed to always produce a valid result.

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

Solution Space

Try it

/**
 * Processes stars in a string: each star removes the nearest non-star
 * character to its left along with itself.
 *
 * @param s String of lowercase letters and '*' characters
 * @returns Resulting string after all star removals
 */
export function removeStars(s: string): string {
  const stack: string[] = [];

  for (const ch of s) {
    if (ch === "*") {
      stack.pop();
    } else {
      stack.push(ch);
    }
  }

  return stack.join("");
}

Approach: stack – iterate through the string; push non-star characters onto the stack, and pop the top on each star.

Time: O(n) – single pass plus O(n) join.

Space: O(n) – the stack can hold up to n characters.

#735 Asteroid Collision

#933 Number of Recent Calls