Removing Stars From a String

Medium
396.

Removing Stars From a String

Removing Stars From a String is a medium coding problem on strings, simulation and stack, asked in Amazon and Adobe interviews.

You are given a string s containing stars *. In one operation you choose a star and remove it together with the closest non-star character to its left.

Apply the operation until no stars remain and return the resulting string. The answer is unique.

Example 1

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

Example 2

Input
s = "erase*****"
Output

Example 3

Input
s = "ab*c"
Output
ac

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters and '*'.
  • The operation is always possible.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var removeStars = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Removing Stars From a String — Problem & Solution

Removing Stars From a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Removing Stars From a String is a medium coding problem on strings, simulation and stack, asked in Amazon and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Simulation, Stack
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s containing stars *. In one operation you choose a star and remove it together with the closest non-star character to its left.

Apply the operation until no stars remain and return the resulting string. The answer is unique.

Example 1

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

Example 2

Input: s = "erase*****"
Output: 

Example 3

Input: s = "ab*c"
Output: ac

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters and '*'.
  • The operation is always possible.

Hints for Removing Stars From a String

  1. Hint 1

    Each star deletes the most recently kept character — that is exactly a stack pop.

  2. Hint 2

    Push letters, pop on a star.

  3. Hint 3

    Whatever is left on the stack, joined in order, is the answer.

How to solve Removing Stars From a String

Each star deletes the most recently kept character — a stack pop.

Approach

  1. Push letters; pop on *.
  2. Join what remains.

Why it works

The closest non-star character to the left of a star is always the current stack top.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The input guarantees every star has a character to remove.

Reference solution

Python

def removeStars(s: str) -> str:
    stack = []
    for ch in s:
        if ch == "*":
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

Java

public static String removeStars(String s) {
    StringBuilder stack = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '*') stack.deleteCharAt(stack.length() - 1);
        else stack.append(c);
    }
    return stack.toString();
}

C++

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

JavaScript

var removeStars = function(s) {
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        if (s.charAt(i) === "*") stack.pop();
        else stack.push(s.charAt(i));
    }
    return stack.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure