Leetcode 316 Solution

This article provides solution to leetcode question 316 (remove-duplicate-letters)
Categories:
Tags:
Access this page by simply typing in "lcs 316" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/remove-duplicate-letters

Solution

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        cnt = collections.defaultdict(int)
        for ch in s:
            cnt[ch] += 1

        stack = []
        added = set()
        for ch in s:
            cnt[ch] -= 1

            if ch in added:
                continue

            while stack and ch < stack[-1] and cnt[stack[-1]] >= 1:
                added.remove(stack[-1])
                stack.pop()

            added.add(ch)
            stack.append(ch)

        return "".join(stack)