Lexicographically Minimum String After Removing Stars

Lexicographically Minimum String After Removing Stars

What is this problem about?

The "Lexicographically Minimum String After Removing Stars interview question" involves a string containing letters and stars ('*'). When you encounter a star, you must remove the star itself along with the smallest character found to its left. If there's a tie for the smallest character, you remove the one with the largest index (the rightmost one). The goal is to find the lexicographically smallest string remaining after all stars are processed. This "Lexicographically Minimum String After Removing Stars coding problem" is a complex variation of stack-based removal problems.

Why is this asked in interviews?

This problem is a great test of data structure selection, specifically the "Heap (Priority Queue) interview pattern" and "Stack interview pattern". Companies like Meta and Amazon use it to see if a candidate can handle multiple constraints (value-based removal and index-based tie-breaking) efficiently in a single pass.

Algorithmic pattern used

You can solve this using 26 stacks or a priority queue. Each of the 26 stacks stores the indices of one specific character ('a' through 'z'). When you see a character, push its index onto its corresponding stack. When you see a star, find the non-empty stack for the smallest character (starting from 'a') and pop the largest index (top of the stack). Finally, collect all remaining indices, sort them, and construct the final string.

Example explanation

String: "caaa*b"

1. 'c' at 0, 'a' at 1, 'a' at 2, 'a' at 3.
2. '*' at 4: Smallest char is 'a'. Rightmost 'a' is at index 3. Remove index 3.
3. 'b' at 5. Remaining indices: 0('c'), 1('a'), 2('a'), 5('b'). Result: "caab".

Common mistakes candidates make

• Removing the wrong 'a': Removing the first 'a' instead of the last one when a star appears.
• Brute force search: Searching for the smallest character manually every time a star is seen, which leads to O(n^2) or O(26*n) complexity.
• Incorrect character tracking: Not keeping track of which indices were deleted, leading to an incorrect final string assembly.

Interview preparation tip

Whenever a problem asks for "smallest value" with a "latest index" tie-breaker, think about using an array of stacks or a specialized priority queue. Breaking the alphabet into 26 discrete buckets is a common and effective strategy in string problems.