🧩 Guide to Solving "Lexicographically Minimum String After Removing Stars" LeetCode 3170 (C++ | JavaScript | Python)

#programming #cpp #javascript #python

Hey, tech explorers! 🌟 Today, let’s decode a delightful greedy string manipulation problem — LeetCode 3170: Lexicographically Minimum String After Removing Stars. We'll walk through a structured approach and implement it step by step in C++, JavaScript, and Python. Let’s go! 🚀

📜 Problem Overview

You’re given a string s containing lowercase letters and asterisks *.

You must repeatedly perform this operation until no * is left:

Remove the leftmost *.
Remove the smallest non-* character to its left. If there are multiple smallest characters, you can choose any.

📝 Goal: Return the lexicographically smallest string after all * and their associated characters have been deleted.

🧠 Intuition & Strategy

This problem is all about greedy decision-making. At every step, you must:

Process characters left to right.
For every *, find the smallest character to its left and remove it.
Make sure you handle characters efficiently — especially for large strings (1 <= s.length <= 10⁵).

We use:

A min-heap to track the smallest character encountered so far.
An index tracker for each character (a to z) to know their positions in the string.
A marking technique (using !) to flag removed characters.
A final pass to build the answer string.

⚙️ C++ Code (Efficient & Clean)

class Solution {
public:
    string clearStars(string s) {
        priority_queue<char, vector<char>, greater<char>> pq;
        vector<vector<int>> indices(26);

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '*') {
                char ch = pq.top();
                s[indices[ch - 'a'].back()] = '!';  // mark as deleted
                indices[ch - 'a'].pop_back();
                if (indices[ch - 'a'].empty()) {
                    pq.pop();  // remove from heap if no more left
                }
            } else {
                if (indices[s[i] - 'a'].empty()) {
                    pq.push(s[i]);  // new character, push into heap
                }
                indices[s[i] - 'a'].push_back(i);
            }
        }

        string res = "";
        for (char c : s) {
            if (c >= 'a') res += c;
        }
        return res;
    }
};

🌐 JavaScript Version

var clearStars = function(s) {
    const indices = Array.from({ length: 26 }, () => []);
    const arr = s.split('');
    const pq = [];

    const pushHeap = (ch) => {
        if (!pq.includes(ch)) {
            pq.push(ch);
            pq.sort();  // simple sort-based heap
        }
    };

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === '*') {
            while (pq.length && indices[pq[0].charCodeAt(0) - 97].length === 0) {
                pq.shift();  // clean up dead entries
            }
            const smallest = pq[0];
            const idx = indices[smallest.charCodeAt(0) - 97].pop();
            arr[idx] = '!';

            if (indices[smallest.charCodeAt(0) - 97].length === 0) {
                pq.shift();
            }
        } else {
            const code = arr[i].charCodeAt(0) - 97;
            if (indices[code].length === 0) pushHeap(arr[i]);
            indices[code].push(i);
        }
    }

    return arr.filter(c => c >= 'a').join('');
};

🐍 Python Version

import heapq
from collections import defaultdict

class Solution:
    def clearStars(self, s: str) -> str:
        s = list(s)
        pq = []
        indices = defaultdict(list)

        for i, ch in enumerate(s):
            if ch == '*':
                while pq and not indices[pq[0]]:
                    heapq.heappop(pq)

                smallest = pq[0]
                idx = indices[smallest].pop()
                s[idx] = '!'  # mark as deleted

                if not indices[smallest]:
                    heapq.heappop(pq)
            else:
                if not indices[ch]:
                    heapq.heappush(pq, ch)
                indices[ch].append(i)

        return ''.join(c for c in s if c >= 'a')

🧪 Test Cases

Input: "aaba*"
Output: "aab"
Explanation: Remove the last 'a' before the '*' for smallest result.

Input: "abc"
Output: "abc"
Explanation: No stars, nothing to remove.

Input: "zz*yy*aa*"
Output: "zya"
Explanation: Always remove the smallest character before each '*'.

Input: "aaab*bbc*"
Output: "aabb"

🧮 Time & Space Complexity

Time Complexity: O(n log k) where k ≤ 26  // Heap operations over 26 letters
Space Complexity: O(n)                   // Position tracking and character marking

✨ Wrap Up

This problem is a wonderful exercise in greedy thinking and priority queues. 💡
By carefully tracking the smallest deletable characters and handling each star in order, we’re able to produce the lexicographically smallest result.

If you found this helpful, drop a ❤️, leave a comment, or follow for more clean walkthroughs!

Happy coding, explorers! 🚀💻