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

Lexicographically Minimum String After Removing Stars

Difficulty: Medium

Problem Description

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters. While there is a '*', do the following operation:

  • Delete the leftmost '*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.

Return the lexicographically smallest resulting string after removing all '*' characters.

Key Insights

  • The problem requires careful management of characters preceding '*' to maintain the lexicographical order.
  • A stack can be utilized to keep track of characters that are not '*', allowing for efficient removal when a '*' is encountered.
  • We should always aim to remove the smallest character available to ensure the resulting string is lexicographically minimal.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the input string. Each character is processed at most once. Space Complexity: O(n) - in the worst case, when there are no '*', we store all characters in the stack.

Solution

To solve the problem, we can use a stack data structure to maintain the current characters of the resulting string. As we iterate through the string:

  1. For each character, if it is not a '*', we simply push it onto the stack.
  2. If we encounter a '*', we pop the smallest character from the stack (if the stack is not empty) to ensure we remove the correct character.
  3. Finally, we construct the resulting string from the characters left in the stack.

This approach ensures we always have the lexicographically smallest string possible after processing all '*' characters.

Code Solutions

def removeStars(s: str) -> str:
    stack = []
    for char in s:
        if char == '*':
            if stack:
                stack.pop()  # Remove the last character from the stack
        else:
            stack.append(char)  # Add the current character to the stack
    return ''.join(stack)  # Join the stack to form the final string
← Back to All Questions