Is Remove Duplicate Letters easy or hard?

Remove Duplicate Letters is typically classified as a medium-level problem. The implementation is not long, but identifying the greedy rule and safely popping characters from a stack requires careful reasoning about future occurrences in the string.

Remove Duplicate Letters Python/Java solution

In Python or Java, implement the greedy stack approach using a list or stack structure along with arrays to track last occurrences and visited characters. Iterate through the string once, pop larger characters that appear later, and append the current character if it hasn't been used yet.

How to solve Remove Duplicate Letters in O(n)?

Record the last index of each character in the string. Iterate through the string and maintain a stack and a visited set. While the stack is not empty and the current character is smaller than the top of the stack and the top appears later again, pop it from the stack. Push the current character if it hasn't been used. This guarantees the lexicographically smallest valid string.

What is the best approach for Remove Duplicate Letters?

The greedy monotonic stack approach is the most efficient solution. Track the last occurrence of each character and iterate through the string once. Maintain a stack and remove larger characters that will appear again later, ensuring the resulting string stays lexicographically smallest. This runs in O(n) time with O(1) extra space.

Is Remove Duplicate Letters asked at Google/Amazon/Meta?

Remove Duplicate Letters frequently appears in interviews at companies like Amazon, Google, and Meta because it tests greedy reasoning and stack usage. Candidates must combine character frequency tracking with a monotonic structure, which is a common pattern in advanced string problems.

What data structure is used in Remove Duplicate Letters?

A stack is the primary data structure used in the optimal solution. The stack maintains the current lexicographically smallest sequence while allowing removal of previously added characters. A hash map or array tracks the last occurrence of each character, and a boolean array or set tracks visited characters.

What is the time complexity of Remove Duplicate Letters?

The optimal solution runs in O(n) time where n is the length of the string. Each character is pushed to and popped from the stack at most once, so the total number of operations is linear. Space complexity is O(1) because the alphabet size is fixed (26 lowercase letters).

Description Hints 1 Solution Video 14:55

316. Remove Duplicate Letters

Medium54.7% acceptance13 companies

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"

Constraints:

1 <= s.length <= 10⁴
s consists of lowercase English letters.

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

Asked at 13 companies

Expedia FactSet Increff Bytedance Paytm Tiktok Zoho

Google Amazon Microsoft Bloomberg D. E. Shaw

+1 more

Topics

Hints open one at a time

Hint 1

Greedily try to add one missing character. How to check if adding some character will not cause problems ? Use bit-masks to check whether you will be able to complete the sub-sequence if you add the character at some index i.

14:55

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution