diff options
author | Jack Sangdahl <[email protected]> | 2025-06-06 19:11:26 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-06 19:11:26 -0600 |
commit | 38025a19a342cb266e766e8cf9aeadfccd8c68ae (patch) | |
tree | ff64ade408c383da842195bfcdac5162a1ac334d /lex_min_str_rem_star.py | |
parent | 285b89a7d901268035bc0faf199b7a5c64f5d787 (diff) | |
download | leetcode-38025a19a342cb266e766e8cf9aeadfccd8c68ae.tar.gz leetcode-38025a19a342cb266e766e8cf9aeadfccd8c68ae.zip |
3170. lexicographically minimum string after removing stars
Diffstat (limited to 'lex_min_str_rem_star.py')
-rw-r--r-- | lex_min_str_rem_star.py | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/lex_min_str_rem_star.py b/lex_min_str_rem_star.py new file mode 100644 index 0000000..04e2cd0 --- /dev/null +++ b/lex_min_str_rem_star.py @@ -0,0 +1,46 @@ +# 3170. Lexicographically Minimum String After Removing Stars +from queue import PriorityQueue + +""" +you are given a string 's'. it may contain any number of '' characters. your +task to remove all '' characters. while there is a '' character, do the +following: 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. +""" + + +class Solution(object): + def clearStars(self, s): + """ + :type s: str + :rtype: str + """ + pq = PriorityQueue() + idx = [[] for i in range(26)] + remove_set = set() + for i in range(len(s)): + if s[i] == "*": + remove_set.add(i) + c = pq.get() + pq.put(c) + remove_set.add(idx[ord(c) - ord("a")][-1]) + del idx[ord(c) - ord("a")][-1] + if len(idx[ord(c) - ord("a")]) == 0: + pq.get() + continue + if len(idx[ord(s[i]) - ord("a")]) == 0: + pq.put(s[i]) + idx[ord(s[i]) - ord("a")].append(i) + ans = "" + for i in range(len(s)): + if i not in remove_set: + ans += str(s[i]) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.clearStars(s="aaba*")) + print(obj.clearStars(s="abc")) |