Solution
Solution 1: Stack
This solution uses a Stack to keep track of the characters that have not been removed. When we encounter a normal character, we add it to the stack. When we encounter a*, we remove the most recently added character from the stack.
The stack follows the Last In, First Out (LIFO) principle, which makes it suitable because each
* removes the closest non-star character to its left.
class Solution {
public String removeStars(String s) {
StringBuilder stack = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '*') {
stack.deleteCharAt(stack.length() - 1);
} else {
stack.append(c);
}
}
return stack.toString();
}
}Solution 2: Reverse Traversal
This approach traverses the string from right to left. We maintain astar counter representing the number of * characters that still need to remove characters.
When we encounter a
*, we increment star. When we encounter a normal character and star > 0, that character is removed, so we decrement star. Otherwise, the character is added to the result.
Since the characters are collected from right to left, we reverse the StringBuilder before returning the result.
class Solution {
public String removeStars(String s) {
char[] arr = s.toCharArray();
StringBuilder sb = new StringBuilder();
int star = 0;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] == '*') {
star++;
} else if (star > 0) {
star--;
} else {
sb.append(arr[i]);
}
}
return sb.reverse().toString();
}
}Complexity
Both solutions process each character once, so the time complexity isO(n), where n is the length of the string.
Both solutions use
O(n) extra space for the resulting StringBuilder.