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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Removing Stars From a String

Number: 2470

Difficulty: Medium

Paid? No

Companies: Google, Amazon, IBM

Problem Description

Given a string s that includes lowercase letters and stars (*), each star requires you to remove itself and the closest non-star character to its left. Continue this operation until there are no stars left, and return the resulting string.

Key Insights

  • Use a stack data structure to simulate the removal operation.
  • When encountering a non-star character, push it onto the stack.
  • When encountering a star, pop the top character from the stack (which represents the nearest non-star character to its left).
  • The final answer is the concatenation of the characters remaining in the stack.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, since we process each character once.
Space Complexity: O(n), in the worst case when no stars are encountered and all characters are stored in the stack.

Solution

The solution employs a stack to efficiently simulate the removal process. As you iterate through the string, push every non-star character onto the stack. When you encounter a star, pop the last character from the stack which represents removing the closest non-star character to its left along with the star. After processing the entire string, join the remaining characters in the stack to form the final result. Critical points include ensuring the operation is performed only when there is a character to remove (guaranteed by problem constraints) and handling the string traversal in a single pass.

Code Solutions

# Python solution for Removing Stars From a String
class Solution:
    def removeStars(self, s: str) -> str:
        result_stack = []  # Initialize a stack to hold characters
        # Iterate through each character in the string
        for char in s:
            if char == '*':
                # When a star is encountered, pop the last character off the stack
                if result_stack:
                    result_stack.pop()
            else:
                # For any normal character, push it onto the stack
                result_stack.append(char)
        # Join the remaining characters to form the final result
        return "".join(result_stack)

# Example usage
# sol = Solution()
# print(sol.removeStars("leet**cod*e"))
← Back to All Questions