How do you solve Remove Duplicate Letters on LeetCode?

Remove Duplicate Letters (LeetCode #316) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a stack allows us to maintain order while ensuring uniqueness.

What is the brute force solution for Remove Duplicate Letters?

The brute force approach for Remove Duplicate Letters is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves generating all possible subsequences of the string and then filtering out duplicates. Finally, we sort these subsequences to find the smallest lexicographical order. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Remove Duplicate Letters?

Remove Duplicate Letters uses the following concepts: String, Stack, Greedy, Monotonic Stack. The recommended patterns to study are: Greedy, Stack.

What are the interview tips for Remove Duplicate Letters?

Explain your thought process clearly while implementing the solution. Consider edge cases, such as strings with all identical characters. Practice writing code for stack-based problems to become comfortable with the approach.

What are common mistakes when solving Remove Duplicate Letters?

Not checking if a character is already in the result stack before adding it. Failing to update the count of characters correctly after processing.

#316

Remove Duplicate Letters

Medium

StringStackGreedyMonotonic StackGreedyStack

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a greedy algorithm with a stack to maintain the characters in the result. We ensure that each character is added only once and in the correct order by checking if we can remove previously added characters to maintain lexicographical order.

⚙️

Algorithm

3 steps

1Step 1: Count the frequency of each character in the string.
2Step 2: Use a stack to build the result string, ensuring each character is added only once.
3Step 3: For each character, if it can be added (not already in the stack), pop characters from the stack that are greater than the current character and can still be found later in the string.

solution.py16 lines

1# Full working Python code
2from collections import Counter
3
4def removeDuplicateLetters(s):
5    stack = []
6    seen = set()
7    count = Counter(s)
8    for char in s:
9        count[char] -= 1
10        if char in seen:
11            continue
12        while stack and char < stack[-1] and count[stack[-1]] > 0:
13            seen.remove(stack.pop())
14        stack.append(char)
15        seen.add(char)
16    return ''.join(stack)

ℹ

Complexity note: The time complexity is O(n) because we traverse the string a constant number of times. The space complexity is O(n) due to the stack and the count array used to track characters.

1Using a stack allows us to maintain order while ensuring uniqueness.
2Greedy choice helps in achieving the smallest lexicographical order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.