Lexicographically Minimum String After Removing Stars - Video Solutions

Problem Overview: You receive a string containing lowercase letters and *. Each star deletes itself and one character to its left. When multiple characters exist to the left, remove the lexicographically smallest one so the final string becomes as small as possible.

Approach 1: Stack to Track Before Deletions (O(n log n) time, O(n) space)

Scan the string from left to right while tracking characters that appear before each *. Maintain a stack (or indexed storage) of characters along with their positions, and use a min‑heap or ordered structure to quickly locate the smallest available character. When you encounter a star, pop the lexicographically smallest character that appears before it and mark both the star and that character for deletion. Continue scanning until the end, then rebuild the string using only characters not removed. The key idea is greedy removal: deleting the smallest possible character before every star guarantees the remaining prefix stays lexicographically minimal. This technique commonly combines stack tracking with a heap (priority queue) to efficiently select the best character to delete.

Approach 2: Two Pointers Technique (O(n) time, O(n) space)

A more optimized method processes the string while maintaining candidate positions for each character. Instead of repeatedly searching, track indices of characters using fixed buckets (for example, 26 lists for each letter). Move through the string with a pointer and record the positions of characters you see. When a * appears, identify the smallest available letter bucket that still has a valid index and remove the most recent occurrence of that letter. This effectively simulates deletions without expensive heap operations. After processing the entire string, reconstruct the result by skipping removed indices. Because each character is inserted and removed at most once, the algorithm runs in linear time. The logic relies on greedy selection and efficient character tracking, a common pattern in string and greedy problems.

Recommended for interviews: The linear two‑pointer/bucket strategy is usually what interviewers expect. It demonstrates that you understand the greedy requirement and can optimize away repeated searches. Starting with the stack + heap idea is still valuable because it clearly models the rule "remove the smallest character before each star" and shows the reasoning before optimizing to O(n).