source: https://leetcode.com/problems/removing-stars-from-a-string/description/
Removing Stars From a String
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*code”
Output: “lecoe”
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is ‘t’ in “leet*code”. s becomes “leecode”.
- The closest character to the 2nd star is ‘e’ in “leecode”. 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 <= 105
- s consists of lowercase English letters and stars *.
The operation above can be performed on s.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public String removeStars(String s) { //use stack Deque<Character> stack = new ArrayDeque<>(); char[] arr = s.toCharArray(); for(char c: arr){ \\ A if(c=='*'){ stack.pop(); } else { stack.push(c); } } StringBuilder sb = new StringBuilder(); while(!stack.isEmpty()){ \\ B sb.append(stack.pollLast()); } return sb.toString(); } } |
Let’s say n is the number of characters in a string
Time Complexity
A + B -> O(2n) -> O(n)
Space Complexity
O(n), storing characters in a deque