Remove Duplicate Letters

By | January 4, 2016
3 Comments
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

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

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

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Solution. We use a nums[] array to record how many times each letter happen in string. We use a stack to store the result. Then we go through each char ch. If ch already visited, then continue. If not visited, and ch is smaller than stack.top() and it still has stack.top() later(nums[stack.top()] > 0), then we pop stack.top().

check my code on github: link

  • junmin liu

    this problem is pretty hard on leetcode, not a medium, i only came out a partial correct solution.

    • http://www.allenlipeng47.com peng li

      as long as we carefully build the stack, it would be solved easily.

      • junmin liu

        either array, stack, linkedlist should be fine. the key is the algorithm itself.