2390. Removing Stars From a String
Removing Stars From a String (LeetCode 2390) 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.
How to solve Removing Stars From a String
Removing Stars From a String is a String Comparison with Backspace Characters problem, part of Two Pointers. Learn to compare strings with backspace characters using two pointers from the end.
Work towards the solution in these steps:
- Use a stack-like structure for characters kept so far.
- When you see '*', remove the most recent kept character.
- Build the answer from remaining characters after one pass.
The reference solution runs in O(n) time and O(n) space.
The Removing Stars From a String solution and editorial walks through the full approach with reference code.
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
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
Removing Stars From a String FAQ
What is the LeetCode number of Removing Stars From a String?
Removing Stars From a String is LeetCode problem 2390, rated Medium.
What pattern is used to solve Removing Stars From a String?
Removing Stars From a String is a String Comparison with Backspace Characters problem. It belongs to the Two Pointers pattern, in the String Comparison with Backspaces subpattern.
What is the time complexity of Removing Stars From a String?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Removing Stars From a String?
Removing Stars From a String has been reported in interviews at Amazon, Google, Meta, Microsoft.