Removing Stars From a String
You are given a string s*
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
Output: "coe"
Explanation: Performing the removals from left to right:
- The closest left side character to the 1st star is 's' in "cs**cod*e".
s- The closest left side character to the 2nd star is 'c' in "c*cod*e".
s- The closest left side character to the 3rd star is 'd' in "cod*e".
sThere are no more stars, so we return "coe".
Example 2
Output: ""
Explanation: The entire string is removed, so we return an empty string.
Constraints:
1 <= s.length <= 105s*- The operation above can be performed on
s
Solution 1 - Using stack, when '*' immediately remove top element from stack
In this approach, we are going to loop through characters of input string sStack'*'**
import java.util.Stack;
import java.util.stream.Collectors;
public class RemovingStarsFromString {
static String removeStars(String s) {
Stack<Character> stack = new Stack<>();
for(char c: s.toCharArray()) {
if('*' == c){
stack.pop();
} else {
stack.push(c);
}
}
return stack.stream().map(String::valueOf).collect(Collectors.joining());
}
public static void main(String[] args) {
System.out.println(removeStars("cs**cod*e"));
System.out.println(removeStars("erase*****"));
}
}Complexity Analysis:
Time complexity: Above code runs in O(n) time.
Space complexity: O(n).
Above implementations source code can be found at