316. Remove Duplicate Letters

Problem Statement

link: LeetCode.cn LeetCode

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Input: s = "bcabc" Output: "abc"

Input: s = "cbacdcbc" Output: "acdb"

Solution Approach

The solution involves utilizing a monotonic stack to greedily select characters while ensuring the resulting string is lexicographically smallest.

Algorithm

1. Initialize Stack: We initialize an empty stack to hold the characters of the resulting string.
2. Iterate Through Characters: Iterate through each character in the input string s.
3. Greedy Selection: For each character.

Implement

    class Solution:
    def removeDuplicatedLetters(self, s):
      stack = []
      remain_counter = collections.Counter(s)
      for c in s:
        if c not in stack:
          while stack and c < stack[-1] and remian_counter[stack[-1]]> 0:
            stack.pop()
          stack.append(c)
        remain_counter[c] -= 1
      return ''.join(stack)
       

    
    

Twitter  facebook  Email