We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Removing Stars From a String

Difficulty: Medium

Problem Description

You are given a string s, which contains stars *. In one operation, you can choose a star in s and 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.

Key Insights

  • Each star represents an operation that removes the last valid character before it.
  • The operations are performed from left to right.
  • The result will always be unique and valid as per the problem constraints.
  • A stack can be effectively used to manage the characters and handle removals.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a stack data structure. We will iterate through each character in the string s. If the character is not a star, we push it onto the stack. If the character is a star, we pop the top character from the stack (which represents removing the closest non-star character to the left). After processing all characters, the stack will contain the resultant characters, which can be joined to form the final string.

Code Solutions

def removeStars(s: str) -> str:
    stack = []
    for char in s:
        if char == '*':
            if stack:  # Only pop if stack is not empty
                stack.pop()  # Remove the closest non-star character
        else:
            stack.append(char)  # Add non-star character to stack
    return ''.join(stack)  # Join the characters in the stack to form the final string
← Back to All Questions