Removing Stars From a String solution and explanation
IBM
Google
9 more videos on this problem
Removing Stars From a String - Leetcode 2390 - PythonNeetCodeIO · 4:54 · 50K views
Removing Stars From a String | Leetcode - 2390 | MICROSOFT | Explanation ➕ Live CodingcodestorywithMIK · 13:14 · 8K views
Leetcode 2390. Removing Stars From a String | Weekly Contest 308.Code with Alisha · 9:40 · 4K views
2390. Removing Stars From a String | Leetcode Weekly Contest 308 | LeetCode 2390Bro Coders · 5:04 · 2K views
Leetcode 2390 Removing Stars From a String | Stacks for Beginners | Coding Decoded SDE SheetCoding Decoded · 4:39 · 1K views
Leetcode 2390 Removing Stars From a String (Java)TheAnalyticGuy · 4:43 · 772 views
2390. Removing Stars From a String - JAVA (Stack + StringBuilder - Detailed explanation)Sourin Majumdar · 7:23 · 416 views
2390. Removing Stars From a String (Leetcode Medium)Programming Live with Larry · 2:41 · 367 views
Removing Stars From a String - Leetcode 2390 - PythonTechError · 4:00 · 313 views
2390. Removing Stars From a String | Leetcode Weekly | Easy | Optimal + BruteforceLit Coder · 8:10 · 132 views
The problem
You are given a string s, which contains stars *.
In one operation, you can:
- Choose a star in
s. - 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 will be generated such that the operation is always possible.
- It can be shown that the resulting string will always be unique.
Example 1:
Input: s = "leet**cod*e" Output: "lecoe" Explanation: Performing the removals from left to right: - The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e". - The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e". - The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe". There are no more stars, so we return "lecoe".
Example 2:
Input: s = "erase*****" Output: "" Explanation: The entire string is removed, so we return an empty string.
Constraints:
1 <= s.length <= 105sconsists of lowercase English letters and stars*.- The operation above can be performed on
s.
Approach overview
Problem Overview: You are given a string where the character * represents a deletion operation. Each star removes the closest non-deleted character to its left along with the star itself. After processing the entire string, return the final string that remains.
This problem is essentially a simulation of deletions while scanning the string. The key challenge is efficiently identifying and removing the most recent valid character when a star appears. Because deletions always target the closest character to the left, the problem naturally maps to a Last-In-First-Out structure.
Approach 1: Stack-based Simulation (O(n) time, O(n) space)
The most direct solution uses a stack to simulate the removal process. Iterate through the string character by character. When you see a regular character, push it onto the stack. When you encounter *, pop the top character from the stack because that represents the closest undeleted character to the left. This works because the most recently added character is exactly the one that should be removed.
After processing all characters, the stack contains the remaining characters in order. Convert the stack back into a string to produce the result. Each character is pushed and popped at most once, so the total time complexity is O(n). The stack can grow up to the length of the string, giving O(n) space complexity. This approach is intuitive and commonly used for problems involving undo-like operations or nested processing in string manipulation.
Approach 2: Two-pointer Technique (O(n) time, O(n) space)
A more space-efficient simulation can be built using the two-pointer technique and processing the string from right to left. The key observation: when you see a star, it will delete one valid character to its left. Instead of immediately removing characters, track how many characters should be skipped.
Traverse the string from the end while maintaining a counter of pending deletions. When you see *, increment the counter. When you see a normal character and the counter is greater than zero, skip the character and decrement the counter because it gets removed by a star. If the counter is zero, keep the character. Append kept characters to a result buffer and reverse it at the end.
This approach still runs in O(n) time because each character is processed once. The extra space for the output string is O(n). It avoids the explicit stack structure and instead relies on pointer traversal and deletion counting, which can feel cleaner in languages where stack operations add overhead.
Recommended for interviews: The stack-based approach is the one most interviewers expect because the deletion rule directly matches stack behavior. Implementing it quickly shows strong intuition for LIFO problems and string simulation. The two-pointer version demonstrates deeper insight into optimizing simulations by reversing traversal and tracking pending operations.
Approach 1: Stack-based Approach
This approach utilizes a stack data structure to handle the character removals efficiently. As we iterate through the string, whenever a star (*) is encountered, we pop from the stack, effectively removing the last non-star character added. This allows us to handle both the star and its preceding non-star character in O(1) time.
def removeStars(s: str) -> str:
result = []
for c in s:
if c == '*':
if result:
result.pop()
else:
result.append(c)
return ''.join(result)
s = "leet**cod*e"
print(removeStars(s))import java.util.*;
public class RemoveStars {
public static String removeStars(String s) {
StringBuilder result = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '*') {
if (result.length() > 0) result.deleteCharAt(result.length() - 1);
} else {
result.append(c);
}
}
return result.toString();
}
public static void main(String[] args) {
String s = "leet**cod*e";
System.out.println(removeStars(s));
}
}#include <iostream>
#include <stack>
using namespace std;
string removeStars(string s) {
string result;
for (char c : s) {
if (c == '*') {
if (!result.empty()) result.pop_back();
} else {
result.push_back(c);
}
}
return result;
}
int main() {
string s = "leet**cod*e";
cout << removeStars(s) << endl;
return 0;
}function removeStars(s) {
const result = [];
for (const char of s) {
if (char === '*') {
if (result.length) result.pop();
} else {
result.push(char);
}
}
return result.join('');
}
console.log(removeStars("leet**cod*e"));#include <stdio.h>
#include <string.h>
char* removeStars(char* s) {
int len = strlen(s);
char* stack = (char*)malloc(len + 1);
int top = 0;
for (int i = 0; i < len; ++i) {
if (s[i] == '*') {
if (top > 0) --top;
} else {
stack[top++] = s[i];
}
}
stack[top] = '\0';
return stack;
}
int main() {
char s[] = "leet**cod*e";
printf("%s\n", removeStars(s));
return 0;
}using System;
using System.Text;
public class Program {
public static string RemoveStars(string s) {
StringBuilder result = new StringBuilder();
foreach (char c in s) {
if (c == '*') {
if (result.Length > 0) result.Remove(result.Length - 1, 1);
} else {
result.Append(c);
}
}
return result.ToString();
}
public static void Main() {
Console.WriteLine(RemoveStars("leet**cod*e"));
}
}In this Python solution, a list is used as a stack to keep track of non-star characters. We pop the last element on encountering a star.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Two-pointer Technique
This alternative method involves using a simple two-pointer technique where we iterate through the string and build the result in place. We treat the string as a writable array and maintain a 'write' index that tells us where to place the next character. When we encounter a star, we just need to move the 'write' index back to overwrite the previous character.
def removeStars(s: str) -> str:
s = list(s)
write = 0
for read in range(len(s)):
if s[read] == '*':
if write > 0:
write -= 1
else:
s[write] = s[read]
write += 1
return ''.join(s[:write])
s = "leet**cod*e"
print(removeStars(s))public class RemoveStars {
public static String removeStars(String s) {
char[] arr = s.toCharArray();
int write = 0;
for (int read = 0; read < arr.length; ++read) {
if (arr[read] == '*') {
if (write > 0) --write;
} else {
arr[write++] = arr[read];
}
}
return new String(arr, 0, write);
}
public static void main(String[] args) {
String s = "leet**cod*e";
System.out.println(removeStars(s));
}
}#include <iostream>
using namespace std;
string removeStars(string s) {
int write = 0;
for (int read = 0; read < s.size(); ++read) {
if (s[read] == '*') {
if (write > 0) --write;
} else {
s[write++] = s[read];
}
}
return s.substr(0, write);
}
int main() {
string s = "leet**cod*e";
cout << removeStars(s) << endl;
return 0;
}function removeStars(s) {
const arr = Array.from(s);
let write = 0;
for (let read = 0; read < arr.length; read++) {
if (arr[read] === '*') {
if (write > 0) write--;
} else {
arr[write++] = arr[read];
}
}
return arr.slice(0, write).join('');
}
console.log(removeStars("leet**cod*e"));#include <stdio.h>
#include <string.h>
char* removeStars(char* s) {
int write = 0;
for (int read = 0; s[read] != '\0'; ++read) {
if (s[read] == '*') {
if (write > 0) --write;
} else {
s[write++] = s[read];
}
}
s[write] = '\0';
return s;
}
int main() {
char s[] = "leet**cod*e";
printf("%s\n", removeStars(s));
return 0;
}using System;
public class Program {
public static string RemoveStars(string s) {
char[] arr = s.ToCharArray();
int write = 0;
for (int read = 0; read < arr.Length; ++read) {
if (arr[read] == '*') {
if (write > 0) --write;
} else {
arr[write++] = arr[read];
}
}
return new string(arr, 0, write);
}
public static void Main() {
Console.WriteLine(RemoveStars("leet**cod*e"));
}
}This Python solution effectively modifies the list of characters in place using two indices, read and write.
Time Complexity: O(n)
Space Complexity: O(1), achieved via in-place operations.
Approach 3: Stack Simulation
We can use a stack to simulate the operation process. Traverse the string s, and if the current character is not an asterisk, push it onto the stack; if the current character is an asterisk, pop the top element from the stack.
Finally, concatenate the elements in the stack into a string and return it.
The time complexity is O(n), where n is the length of the string s. Ignoring the space consumption of the answer string, the space complexity is O(1).
function removeStars(s: string): string {
const ans: string[] = [];
for (const c of s) {
if (c === '*') {
ans.pop();
} else {
ans.push(c);
}
}
return ans.join('');
}func removeStars(s string) string {
ans := []rune{}
for _, c := range s {
if c == '*' {
ans = ans[:len(ans)-1]
} else {
ans = append(ans, c)
}
}
return string(ans)
}impl Solution {
pub fn remove_stars(s: String) -> String {
let mut ans = String::new();
for &c in s.as_bytes().iter() {
if c == b'*' {
ans.pop();
} else {
ans.push(char::from(c));
}
}
ans
}
}class Solution {
/**
* @param String $s
* @return String
*/
function removeStars($s) {
$ans = [];
$n = strlen($s);
for ($i = 0; $i < $n; $i++) {
$c = $s[$i];
if ($c === '*') {
array_pop($ans);
} else {
$ans[] = $c;
}
}
return implode('', $ans);
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-based Approach | Time Complexity: O(n) |
| Two-pointer Technique | Time Complexity: O(n) |
| Stack Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-based Simulation | O(n) | O(n) | Best general solution. Clear mapping between '*' and stack pop operations. |
| Two-pointer Technique (right-to-left) | O(n) | O(n) | Useful when simulating deletions by counting operations instead of storing a stack. |
Frequently asked questions
Is Removing Stars From a String easy or hard?
The problem is rated Medium on LeetCode but is often considered an easier medium question. The logic becomes straightforward once you recognize the stack pattern where '*' behaves like an undo operation that removes the most recent character.
Removing Stars From a String Python/Java solution
In Python, use a list as a stack and append characters while popping when '*' appears. In Java, use a StringBuilder or a Deque to simulate stack operations. Both implementations achieve O(n) time and O(n) space complexity.
How to solve Removing Stars From a String in O(n)?
Traverse the string once and simulate deletions. Using a stack, push normal characters and pop when encountering '*'. Another O(n) method scans from right to left using a counter that tracks how many characters should be skipped due to stars.
What is the best approach for Removing Stars From a String?
The stack-based approach is the most common and intuitive solution. Iterate through the string, push characters onto a stack, and pop the top element whenever a '*' appears. This directly simulates removing the closest character to the left and runs in O(n) time with O(n) space.
Is Removing Stars From a String asked at Google/Amazon/Meta?
Problems involving stack-based string processing and simulation are common in interviews at companies like Amazon, Google, and Meta. Variations of this problem appear in interview practice sets because they test understanding of stacks, string traversal, and efficient simulation.
What data structure is used in Removing Stars From a String?
A stack is the primary data structure used to solve the problem efficiently. The stack stores characters as they appear, and when a '*' is encountered the most recent character is removed using a pop operation. This matches the problem's requirement of deleting the closest character to the left.
What is the time complexity of Removing Stars From a String?
The optimal solutions run in O(n) time where n is the length of the string. Each character is processed once, and stack operations such as push and pop are O(1). The overall space complexity is O(n) because the result or stack can store up to n characters.