Python -> stack based solution with detailed explanation


  • 1
    M

    This is a stack based solution.
    1> First I go over all the letters and add it to dictionary along with their counts of appearance.
    2> I use a list as stack to store all the lexicographically arranged result set until i'th index where 0 <= i < len(input_array).
    3> I initialize a visited set to keep track of all elements that are already there in stack. Whenever I come across the same element which is already there in stack, I do not bother to do any operation except for decreasing its counter.
    4> If the stack is empty, I just add the element as is.
    5> if the letter under inspection is lesser than the elements on the top of the stack, then I continue to pop them out of stack but on one condition:
    -> If the stack letter counter is 0, I do not dare to remove it.
    If the stack letter counter is ZERO, I know that the element has no chance to appear in future. Hence I keep it as is in the stack and append our new letter on to the stack.
    6> Also, whenever I remove any element from the stack, I have to ensure they are removed from the visited set as well so in the future I can add them back to stack.

        def removeDuplicateLetters(self, s):
            """
            :type s: str
            :rtype: str
            """
            ldict = {}
            
            for letter in s:
                ldict[letter] = ldict.get(letter, 0) + 1
            stack = []
            visited = set()
            for letter in s:
                if not stack:
                    stack.append(letter)
                    ldict[letter] -= 1
                    visited.add(letter)
                    continue
                if letter not in visited:
                    while stack and letter < stack[-1] and ldict[stack[-1]] > 0:
                        oldLetter = stack[-1]
                        stack.pop()
                        visited.remove(oldLetter)
                    stack.append(letter)
                    visited.add(letter)
                ldict[letter] -= 1
            
            return "".join(stack)```

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.