Removing Stars From a String

Removing Stars From a String is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the String Comparison with Backspaces subpattern.

Problem statement

You are given a string s, which contains stars .

In one operation, you can:

1. Choose a star in s. 2. Remove the closest non-star character to its left, as well as remove the star itself.

Return the string after all stars have been removed.

Note: - The input is generated such that the operation is always possible. - It can be shown that the resulting string is always unique.

Example 1: - Input: s = "leetcode" - Output: "lecoe" - Explanation: - Remove t with 1st : leecode - Remove e with 2nd : lecode - Remove d with 3rd : lecoe

Example 2: - Input: s = "erase" - Output: ""

Constraints: - 1 <= s.length <= 10^5 - s consists of lowercase English letters and stars . - The operation above can be performed on s.

Topics and companies

Topics: Stack, String, Simulation, Two Pointers.

Reported in interviews at Amazon, Google, Meta, Microsoft.

How to practise Removing Stars From a String on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 3 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Removing Stars From a String in the code editor, or read the Removing Stars From a String editorial for a worked solution with its approach and complexity analysis.

Where Removing Stars From a String sits in the DSA pattern sheet

• Two Pointers pattern guide
• String Comparison with Backspaces subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Removing Stars From a String

Other problems that use the same String Comparison with Backspaces and Two Pointers techniques:

• Backspace String Compare — Easy, same subpattern
• Crawler Log Folder — Easy, same subpattern
• Boats to Save People — Medium, same pattern
• Container With Most Water — Medium, same pattern
• Delete the Middle Node of a Linked List — Medium, same pattern
• Find the Duplicate Number — Medium, same pattern