Give you a string s
, Please remove the duplicate letters from the string , Make each letter appear only once . To be guaranteed The dictionary order of the returned result is the smallest ( The relative position of other characters should not be disturbed ).
example :
Input :s = "cbacdcbc"
Output :"acdb"
analysis :
The subject of the topic is de duplication , Then it requires that the lexicographic order of the returned results be minimized , Is to ensure that each character appears only once , Try to make the strings orderly , From small to large .
The method is to design a stack , If it is stored in the stack, skip , If not , Then judge first , Whether the top element of the stack can be taken out , If characters following string include top of stack elements , And the stack top element is larger than the current element , Then you can take out the top element of the stack , Then put the current element in , In this way, local sorting can be realized , And subsequent elements will be supplemented .、
Code :
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s) # String length
stack = [] # Create a stack
for i in range(n): # Traversal string
if s[i] in stack: # The current character has been stored in the stack
continue
else: # The current character has not been stored on the stack
while stack and stack[-1] > s[i] and stack[-1] in s[i + 1:]: # The stack is not empty and the top of the stack element is larger than the current element and the top of the stack element exists in subsequent elements ( Otherwise, it cannot be supplemented )
stack.pop() # Pop up top element
stack.append(s[i]) # Stack the current element
return ''.join(stack) # Connect the elements in the stack into a string