[LeetCode] 2390. Removing Stars From a String

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

 

 

How to Think of the Solution

' Iterate Through the String

- Traverse the input string s character by chracter

- For each character, decide:

  - if it is a '*', pop the top of the stack (remove the last character)

  - Otherwise, push the character onto the stack

 

When to Use a STack

A stack is a good fit for problems involving:

- Undo Operations: When elements must be removed or undone in reverse order of their addttion.

- Matching Parentheses or Brackets : Checking validity of nested structures.

- Backtracking Scenarios : Such as traversing paths, rolling back to a previous state, or managing nested operations.

 

Join Method

- ''.join(stack) taks all elements in the list stack and joins them into a single string with no seperator(empty string '')

- The syntax is 'separator'.join(iterable)

 

class Solution:
    def removeStars(self, s: str) -> str:
        stack = []
        for ch in s:
            if ch == '*':
                stack.pop()
            else:
                stack.append(ch)
        
        return ''.join(stack)