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:
'*' 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 <= 105s consists only of lowercase English letters and '*'.'*' characters.class Solution {
public String clearStars(String s) {
int n = s.length();
char[] cs = s.toCharArray();
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
for (int i = 0; i < n; i++) {
if (cs[i] == '*')
cs[pq.poll()[1]] = '*';
else
pq.offer(new int[] { cs[i] - 'a', i });
}
return new String(cs).replace("*", "");
}
}class Solution {
public String clearStars(String s) {
int n = s.length();
char[] cs = s.toCharArray();
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
for (int i = 0; i < n; i++) {
if (cs[i] == '*')
cs[pq.poll()[1]] = '*';
else
pq.offer(new int[] { cs[i] - 'a', i });
}
return new String(cs).replace("*", "");
}
}