Skip to content

← leetcode

Lexicographically Minimum String After Removing Stars

· Medium

LeetCode problem 3170

My initial solution was basically, we can sort all the letters in a priority queue in the order at which they should be getting removed from s if an asterisk was to appear.

Then, keeping like a bitmap of all the letters that still remain after one pass of the string, we can construct what the resulting string should look like after removing all * characters.

code

class Solution {
public:
    string clearStars(string s) {
        auto comparator = [&](auto first, auto second) {
            if (first.first != second.first) {
                return first.first > second.first;
            } else {
                return first.second < second.second;
            }
        };
        vector<bool> bitmap (s.size(), true);
        priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(comparator)> pq(comparator);
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != '*') {
                pq.push({s[i], i});
            } else {
                bitmap[i] = false;
                bitmap[pq.top().second] = false;
                pq.pop();
            }
        }
        string ans = "";
        for (int i = 0; i < s.size(); ++i) {
            if (bitmap[i]) {
                ans += s[i];
            }
        }
        return ans;
    }
};

complexity

  • Time: O(n log (n)) where n is the size of the string s
  • Space: O(n)

learnings

The other solution that I saw revolved around keeping 26 stacks (for each letter of the alphabet) and only popping from the smallest stack.

NOTE: wait... I do not need another bitmap array... I can just swap out removed letters in s with an asterisk...

class Solution {
public:
    string clearStars(string s) {
        vector<stack<int>> lastLetter(26);

        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != '*') {
                lastLetter[s[i]-'a'].push(i);
            } else {
                for (int i = 0; i < 26; ++i) {
                    if (!lastLetter[i].empty()) {
                        s[lastLetter[i].top()] = '*';
                        lastLetter[i].pop();
                        break;
                    }
                }
            }
        }

        string ans = "";
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != '*') {
                ans += s[i];
            }
        }
        return ans;
    }
};

and an improved version of the original solution above (removing the bitmap array and just replacing the deleted letters in-place with an asterisk *):

class Solution {
public:
    string clearStars(string s) {
        auto comparator = [&](auto first, auto second) {
            if (first.first != second.first) {
                return first.first > second.first;
            } else {
                return first.second < second.second;
            }
        };
        priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(comparator)> pq(comparator);
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != '*') {
                pq.push({s[i], i});
            } else {
                s[pq.top().second] = '*';
                pq.pop();
            }
        }
        string ans = "";
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != '*') {
                ans += s[i];
            }
        }
        return ans;
    }
};

time taken

  • 15 minutes and 50 second