-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path316.py
More file actions
29 lines (25 loc) · 799 Bytes
/
316.py
File metadata and controls
29 lines (25 loc) · 799 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from collections import Counter, defaultdict
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
char_cnt = Counter(s)
visited = defaultdict(bool)
stack = []
for char in s:
if not visited[char]:
while stack and stack[-1] > char and char_cnt[stack[-1]]:
prv = stack.pop()
visited[prv] = False
stack.append(char)
visited[char] = True
char_cnt[char] -= 1
return ''.join(stack)
if __name__ == '__main__':
cases = [
('bcabc', 'abc'),
('cbacdcbc', 'acdb'),
]
sln = Solution()
for s, golden in cases:
res = sln.removeDuplicateLetters(s)
print(golden, res)
assert golden == res