3445. Lexicographically Minimum String After Removing Stars¶

Difficulty: Medium

LeetCode Problem View on GitHub

3445. Lexicographically Minimum String After Removing Stars

Medium

You are given a string s. It may contain any number of '*' characters. Your task is to remove all '*' characters.

While there is a '*', do the following operation:

Delete the leftmost '*' and the smallest non-'*' character to its left. If there are several smallest characters, you can delete any of them.

Return the lexicographically smallest resulting string after removing all '*' characters.

Example 1:

Input: s = "aaba*"

Output: "aab"

Explanation:

We should delete one of the 'a' characters with '*'. If we choose s[3], s becomes the lexicographically smallest.

Example 2:

Input: s = "abc"

Output: "abc"

Explanation:

There is no '*' in the string.

Constraints:

1 <= s.length <= 10⁵
s consists only of lowercase English letters and '*'.
The input is generated such that it is possible to delete all '*' characters.

Solution¶

class Solution {
    public String clearStars(String s) {
        int n = s.length();
        PriorityQueue<Pair> pq = new PriorityQueue<>(new sorting());
        HashSet<Integer> deleted = new HashSet<>();
        for(int i = 0; i < n; i++){
            if(s.charAt(i) != '*') {
                pq.offer(new Pair(s.charAt(i) , i));
            }
            else {
                if(pq.size() == 0) continue;
                deleted.add(pq.peek().ind);
                pq.poll();
            }
        }

        String ans = "";
        for(int i = 0; i < n; i++) {
            if(!deleted.contains(i) && s.charAt(i) != '*') {
                ans += s.charAt(i);
            }
        }
        return ans;
    }

    static class Pair {
        char ch;
        int ind;
        public Pair(char ch, int ind) {
            this.ch = ch;
            this.ind = ind;
        }
    }

    static class sorting implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            int op1 = Integer.compare(first.ch, second.ch);
            if(op1 != 0) return op1;
            return Integer.compare(second.ind , first.ind);
        }
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here