316. Remove Duplicate Letters 🔥

Medium

Problem:

List the characters in lexicographical order, excluding duplicates.

Input: s = "ebcabc"
Output: "eabc"
Input: s = "ebcabce"
Output: "abce"

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

What to learn:

Similar python technique

• 49. Group Anagrams

• 819. Most Common Word

Solution:

Recursion

Similar to divide and conquer, the size of the suffix gradually decreases, and when nothing is left, it backtracks and the results are combined.

1. Use a set to exclude duplicate characters and sort the input string in alphabetical order.

2. Separate the suffix.

3. If the entire set matches the suffix set, use recursion to separate them.

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters(suffix.replace(char, ""))
        return ""

Stack

I only used operations defined in the stack ADT.

1. Push the characters onto the stack in the same order as the input string.

2. Skip the character if it already exists in the stack.

3. If the current character, char, is lexicographically preceding the character on the stack and the character on the stack appears later in the string, remove the character from the stack.

class Solution:
    def removeDuplicateLetters(s: str) -> str:
        counter, stack, seen = collections.Counter(s), [], set()
    
        for char in s:
            counter[char] -= 1
            if char in seen:
                continue
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                seen.remove(stack.pop())
            stack.append(char)
            seen.add(char)
        return "".join(stack)

If we were not to limit the solution to using the stack data structure

Here, we used the in search operation to find out whether a character has been processed or not. This operation does not exist in the stack.

class Solution:
    def removeDuplicateLetters(s: str) -> str:
        counter, stack = collections.Counter(s), []
    
        for char in s:
            counter[char] -= 1
            if char in stack:
                continue
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
            stack.append(char)
        return "".join(stack)