Stack - 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.

Input: s = "cs**cod*e"
Output: "coe"
Explanation: Performing the removals from left to right:
- The closest left side character to the 1^st star is 's' in "cs**cod*e". s becomes "c*cod*e".
- The closest left side character to the 2^nd star is 'c' in "c*cod*e". s becomes "cod*e".
- The closest left side character to the 3^rd star is 'd' in "cod*e". s becomes "coe".
There are no more stars, so we return "coe".

Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters and stars *.
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 s and add them to Stack, and when the symbol '*' occurred, we will remove the top element from the stack, this is nothing but the left side character of * symbol, the reason we choose a stack is because there could be many *'s and we have to perform removing left side characters for all the occurrences of this symbol. (For example, look at example look at example 2 above).

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 GitHub link for Java code

Constraints:

Contents

Complexity Analysis: