Removing Stars From a String

MediumStackstack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a string s of lowercase letters and stars '*'. Each star deletes itself together with the **closest non-star character to its left** that has not already been deleted. Process the stars from left to right. The input is guaranteed to always have such a character available for every star. Return the string that remains (it may be empty). Aim for O(n) time.

Examples

Input: s = "ab*c**d"
Output: "d"
The first star removes b ("ac" so far), the next two remove c and a, leaving "d".
Input: s = "xyz*"
Output: "xy"
The star removes z.

Constraints

  • 1 <= s.length <= 10^5
  • s contains only lowercase English letters and '*'
  • Every star has a non-deleted letter to its left when processed

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More stack problems