Given a string containing only lowercase letters, remove duplicate letters from the string so that each letter appears only once. Ensure that the lexicographic order of the returned result is minimal (the relative position of other characters must not be disturbed).

Example 1:

Input: bcabc Output: ABC Example 2:

Input: “cbacdcbc”

Output: “acdb”

The problem requires that duplicate letters be removed from the string, even though each letter in the string may appear only once. At the same time, ensure that the lexicographical order of the final string is minimum, and the sequence of the letters in the final string cannot be changed.

Therefore, we need to iterate over the string, while using the stack to hold the currently iterated characters:

  • If the current character is not on the stack, it is pushed onto the stack
  • If the current character is already in the stack, the current character is repeated and continues to iterate

After the above process, the characters in the stack are definitely not duplicated, and the relative order between the characters is guaranteed, but it may not be lexicographically minimal. For example, for instance 1BCABC, the algorithm execution flow is as follows:


The correct result would be ABC. You can see that both b and C lexicographs are larger than A when A is pushed, and they exist in the rest of the string. So, when iterating over a character that does not exist in the stack:

  • If the current character is smaller than the top character dictionary order, and the top character still exists in the rest of the string, then the top element should go off the stack

  • The current character is pushed onto the stack until the stack is empty or the lexicographical order of the top element is smaller than the current character


To determine whether the top character of the stack exists in the rest of the string, hash table can be used to count the number of non-repeating characters and occurrences in the original string, or in can be used to judge, but the time complexity of hash table is lower.

So, the complete code looks like this:

class Solution:
    def removeDuplicateLetters(self, s: str) - >str:
        if not s: return ""

        d = Counter(s)
        stack = []
        for i in list(s):
        	# Count -1 for each character accessed
            d[i] -= 1
            if i in stack:
               continue
            else:
                while stack and i < stack[-1] and d[stack[-1]] > 0:
                    stack.pop()
            
                stack.append(i)

        return str(' '.join(stack))
Copy the code