Q316. Remove Duplicate Letters

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.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

 

Example 1:

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

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

Constraints:

1 <= s.length <= 104
s consists of lowercase English letters.

I think this question definitely fits into “Need to Know” category. It uses clever trick which I did not get it initially.

It turns out that we could do this greedily. From left to right, when we get increasing characters in a row, we don’t need to do any further thing. But when a small character occurs, we want to start over from the small one if the previous characters re-occur in the subsequent strings. But what if some characters do not occur again? It suggests that they should be at least at the current position or even occur earlier. But since the previous string is increasing, to keep the not re-occurring character at the current position is the best solution.

OK, let’s wrap up the idea above into an algorithm. First we need to know if the character is re-occurring after a position. To do so, we can record the last position of each character. Another detail is that whenever we saw a character that have already occurred in the current string, we safely ignore it since to start over at the new one won’t give better solution that the current one.

Summing up, the algorithm is:

1. At position j, if s[j] is not in the current stack (use a dict to maintain this):

   • If s[j] > stack[-1], append s[j] to the end of stack
   • If s[j] < stack[-1] and last_position[stack[-1]] > j, pop the top one in the stack until one of the two conditions s[j] < stack[-1] and last_position[stack[-1]] > j do not hold.

2. The stack contains the solution.

The Python submission is:

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        
        if len(s) <= 1:
            return s
        
        n_occur_dict = {}
        for j in range(len(s)):
            n_occur_dict[s[j]] = j
        
        memory = {}
        mystack = []
        for j in range(len(s)):
            if s[j] not in memory:
                if len(mystack) == 0 or s[j] > mystack[-1]:
                    pass
                else:
                    while len(mystack) > 0 and s[j] < mystack[-1] and n_occur_dict[mystack[-1]] > j:
                        del memory[mystack.pop()]
                memory[s[j]] = 1
                mystack.append(s[j])
        res = ''
        for i in memory:
            res += i
        return res