aboutsummaryrefslogtreecommitdiff
path: root/lex_min_str_rem_star.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-06 19:11:26 -0600
committerJack Sangdahl <[email protected]>2025-06-06 19:11:26 -0600
commit38025a19a342cb266e766e8cf9aeadfccd8c68ae (patch)
treeff64ade408c383da842195bfcdac5162a1ac334d /lex_min_str_rem_star.py
parent285b89a7d901268035bc0faf199b7a5c64f5d787 (diff)
downloadleetcode-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.py46
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"))