Remove Duplicate Letters - Leetcode Solution

Problem statement:

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.

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

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

Solution approach:

The key point of this question is to find the smallest lexicographical order after removing the duplicate letters. Here’s the approach that can help in solving the problem -

1. Create a character frequency map to store the frequency of each character in the given string.

2. Use a stack to maintain the characters that will be part of the final solution.

3. Initialize an empty visited set to keep track of which characters are in the stack.

4. Traverse the given string and for each character, do the following -

   a. Decrement its frequency in the frequency map.

   b. If it already exists in the visited set, then continue.

   c. If the character is smaller than the top element of the stack and the top element of the stack still has frequency remaining in the frequency map, then pop it from the stack and remove it from the visited set.

   d. Push the current character into the stack and add it to the visited set.

5. After traversal, create a final string by popping all the elements from the stack while appending them to the solution in reverse order.

6. Return the final string.

Here’s the code implementation of the above approach -

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        
        # Step 1: Create a character frequency map.
        char_freq_map = {}
        for char in s:
            if char not in char_freq_map:
                char_freq_map[char] = 0
            char_freq_map[char] += 1
            
        # Step 2: Use a stack to maintain the characters that will be part of the final solution.    
        stack = []
        
        # Step 3: Initialize an empty visited set.
        visited = set()
        
        # Step 4: Traverse the given string.
        for char in s:
            # Decrement the frequency of the current character.
            char_freq_map[char] -= 1
            
            # If the current character already exists in the visited set, then continue.
            if char in visited:
                continue
                
            # If the current character is smaller than the top element of the stack and the top element of the stack
            # still has frequency remaining in the frequency map, then pop it from the stack and remove it from the
            # visited set.
            while stack and char < stack[-1] and char_freq_map[stack[-1]] > 0:
                visited.remove(stack.pop())
                
            # Push the current character into the stack and add it to the visited set.
            stack.append(char)
            visited.add(char)
        
        # Step 5: Create a final string by popping all the elements from the stack while appending them to the solution
        # in reverse order.
        final_string = ''
        while stack:
            final_string += stack.pop()
            
        # Step 6: Return the final string.
        return final_string[::-1]

Time Complexity:

The time complexity of the above solution is O(N), where N is the length of the input string.

Space Complexity:

The space complexity of the above solution is O(1), because the frequency map and visited set both can have at most 26 unique characters, so constant space is used. The stack and the final string can also have at most N elements, where N is the length of the input string.

1