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

Lexicographically Minimum String After Removing Stars

Number: 3445

Difficulty: Medium

Paid? No

Companies: Flexera

Problem Description

Given a string s that contains lowercase English letters and some '' characters, you must repeatedly perform the following operation: While there is a '' in the string, remove the leftmost '' and, among the characters to its left that have not been removed, delete the smallest letter (i.e. the letter that is lexicographically smallest). In case of a tie among the smallest letters, you are allowed to choose any; however, to obtain the lexicographically smallest final result, the optimal choice is to remove the rightmost occurrence among those smallest letters. After all '' characters have been processed (and removed), return the lexicographically smallest resulting string.

Key Insights

  • The process removes exactly as many letters as there are '*' characters.
  • Each star forces the removal of one letter from those appearing before it.
  • When there is more than one occurrence of the smallest letter among the eligible letters, deleting the one that appears as far to the right as possible tends to yield a lexicographically smaller final string.
  • We can simulate the process by scanning s from left to right while maintaining a data structure of “active” (not-yet-deleted) letters.
  • Use “buckets” (one per lowercase letter from 'a' to 'z') to quickly find and remove the smallest available letter for each star.

Space and Time Complexity

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

Solution

The idea is to simulate the removal operations as described. As we scan s from left to right, we keep an “active list” of letters that have been seen and not yet removed. For each letter that is read, we append it to the active list and also record its position in a bucket corresponding to that letter (each bucket holds the indices in the active list where that letter occurs). When we encounter a '*', we iterate over the letters from 'a' to 'z' (which is constant, 26 letters) and pick the first bucket that is non-empty. From that bucket we remove the last index (i.e. the rightmost occurrence among available ones) and mark that letter as removed in our active list. After processing the entire string, the final answer is obtained by collecting the letters in the active list that were not marked as removed, preserving their original order.

Important details/tricks:

  • By choosing the rightmost occurrence in the bucket for the smallest letter, we “delay” the gap in the final string so that earlier positions (which affect the lexicographic order more) are left intact.
  • Buckets provide an O(1) check (constant cost per star, 26 letters at most) for the candidate letter.
  • We use an auxiliary array (the active list) that holds the letters; when a letter is “deleted,” we mark it (for example, by setting its value to an empty marker) rather than removing it immediately to maintain order.

Code Solutions

# Python code solution with detailed comments
def removeStars(s: str) -> str:
    # active will store the letters in order of appearance.
    active = []
    # bucket mapping from letter to a list of indices in 'active' where that letter appears.
    buckets = {chr(c): [] for c in range(ord('a'), ord('z')+1)}
    # For each character in the string
    for char in s:
        if char != '*':
            # Append the letter to active list and record its index in the corresponding bucket.
            active.append(char)
            buckets[char].append(len(active) - 1)
        else:
            # When encountering a '*', find the smallest letter available in buckets.
            for letter in (chr(c) for c in range(ord('a'), ord('z')+1)):
                if buckets[letter]:
                    # Pop the rightmost index from the bucket for that letter.
                    remove_idx = buckets[letter].pop()
                    # Mark that position as removed in active by setting a placeholder.
                    active[remove_idx] = ""
                    break
    # Join and return the letters that are not removed.
    return "".join(letter for letter in active if letter != "")
    
# Example usage
if __name__ == "__main__":
    s = "aaba*"
    print(removeStars(s))  # Output: "aab"
← Back to All Questions