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 <= 40s consists of lowercase English letters and '*'.The operation is always possible.
Hints for Removing Stars From a String
Hint 1
Each star deletes the most recently kept character — that is exactly a stack pop.
Hint 2
Push letters, pop on a star.
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
- Push letters; pop on
*. - 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