Lexicographically Minimum String After Removing Stars Python/Java solution

In Python or Java, maintain lists or stacks storing indices of characters. When a '*' appears, remove the smallest available character index and mark it as deleted. After the scan, rebuild the string using characters whose indices were not removed. The optimized implementation runs in O(n) time.

What is the best approach for Lexicographically Minimum String After Removing Stars?

The optimal approach uses a greedy strategy with indexed character tracking (often implemented with 26 buckets or stacks). Each time a '*' appears, remove the smallest lexicographic character that exists to its left. Because every character is processed and removed at most once, this approach runs in O(n) time with O(n) space.

Is Lexicographically Minimum String After Removing Stars asked at Google/Amazon/Meta?

Problems combining greedy logic with stacks, heaps, or string manipulation are common in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your ability to maintain ordering constraints while processing deletions efficiently.

What data structure is used in Lexicographically Minimum String After Removing Stars?

Typical solutions use stacks to track characters before a star and either a min‑heap or fixed character buckets to quickly find the smallest letter. These structures support efficient deletions while scanning the string from left to right.

What is the time complexity of Lexicographically Minimum String After Removing Stars?

The optimized greedy solution runs in O(n) time and O(n) space, where n is the length of the string. Each character is inserted once and removed at most once. A simpler implementation using a priority queue takes O(n log n) time because every deletion requires a heap operation.

Description Solution Video 23:42

3170. Lexicographically Minimum String After Removing Stars

Q: Is Lexicographically Minimum String After Removing Stars easy or hard?

The problem is rated Medium on LeetCode. The difficulty comes from combining greedy choice with efficient tracking of the smallest available character. A naive simulation is simple, but optimizing it to O(n) requires careful use of stacks or indexed buckets.

Q: How to solve Lexicographically Minimum String After Removing Stars in O(n)?

Traverse the string while storing indices of characters in 26 buckets (one for each letter). When you encounter '*', locate the smallest bucket that still contains an index and remove the most recent occurrence of that character. Mark both the star and the removed character, then reconstruct the final string. Since each index is handled once, the overall complexity stays O(n).

Medium51.0% acceptance7 companies

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.

Example 1:

Input: s = "aaba*"

Output: "aab"

Explanation:

We should delete one of the 'a' characters with '*'. If we choose s[3], s becomes the lexicographically smallest.

Example 2:

Input: s = "abc"

Output: "abc"

Explanation:

There is no '*' in the string.

Constraints:

1 <= s.length <= 10⁵
s consists only of lowercase English letters and '*'.
The input is generated such that it is possible to delete all '*' characters.

Asked at 7 companies

Flexera Salesforce Amazon

Google Microsoft Meta Bloomberg

Topics

23:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def clearStars(self, s: str) -> str:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"aaba*"

Input

"abc"

Your code is saved on this device.Solution