Leetcode 3170 | Lexicographically Minimum String After Removing Stars | Priority Queue Java Solution

In this video, we solve Leetcode Problem 3170 - Lexicographically Minimum String After Removing Stars using a greedy approach with a priority queue in Java.

🔹 Problem Summary:
You're given a string s made up of lowercase letters and '*' characters.
Each time a '*' is encountered, you must remove the lexicographically smallest character that appears before it.
Your task is to return the final string after applying all '*' operations.

🔹 Approach:

Use a priority queue (min-heap) to always get the smallest character seen so far.

Maintain character indices in the heap to track what gets removed.

When a '*' is found, remove the smallest character from the heap and mark it using a boolean array.

In the end, rebuild the string by skipping removed characters and all '*'.

🧠 Time Complexity:

O(n log n) — Each insert/remove operation in the priority queue takes log n, and we can have up to n such operations.

🧠 Space Complexity:

O(n) — For the priority queue and the isRemoved array.