Using a Heap to Remove '*' and the Smallest Character from a String

Problem Introduction

• Problem: LeetCode No. 3170, Medium Level
• The string S may contain any number of '*' characters
• Task: Remove all '*' characters
• While removing '*', the smallest non-star character to its left should also be removed
• Result: Return the lexicographically smallest resultant string

Example and Approach

• Explain the solution to the problem with an example
• On encountering '*', find the smallest non-star character on its left and remove it
• 'ABA' is the correct answer if '*' and 'A' are removed first

Basic Thought Process

• Store non-star characters in the smallest order
• A brute force solution will not work as it is not optimal
• Use a heap to solve the problem

Use of Heap

• Use a min-heap that can give us the smallest character in O(1) time
• Keep the lexically smallest character at the top of the heap
• Store the smallest character with its index to keep track of the left position

Detailed Approach

• As we traverse, add non-star characters along with their positions in the heap
• On encountering '', pop the top of the heap and use that position to update string by removing ''
• Construct the new string after removing all '*'

Coding Approach

1. Extract the length of the string
2. Define a priority queue (heap)
3. Define a custom comparator function that ensures the smallest character and then the largest index
4. Traverse the string: if '*', pop the smallest character else push into the heap
5. Compile the leftover string after removing all *

Code Structure

int n = s.length();
priority_queue<pair<char, int>, vector<pair<char, int>>, comparator> pq;
struct comparator {
    bool operator()(pair<char, int>& p1, pair<char, int>& p2) {
        if (p1.first == p2.first) return p1.second < p2.second;
        return p1.first > p2.first;
    }
};

for (int i = 0; i < n; ++i) {
    if (s[i] != '*') {
        pq.push({s[i], i});
    } else {
        auto [char, idx] = pq.top();
        pq.pop();
        s[idx] = '*';
    }
}

string result;
for (int i = 0; i < n; ++i) {
    if (s[i] != '*') result.push_back(s[i]);
}

Time and Space Complexity

• Time: O(n log n)
• Space: O(n)