#316

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Remove Duplicate Letters

Remove duplicate letters from a string to produce the lexicographically smallest result using stack-based state management.

string stack greedy monotonic stack

Problem Statement

Given a string s consisting of lowercase English letters, remove duplicate letters so that each letter appears exactly once. You must return the result that is the smallest in lexicographical order among all possible results while preserving relative character order.

For example, given s = "bcabc", the correct output is "abc". For s = "cbacdcbc", the correct output is "acdb". Constraints: 1 <= s.length <= 10^4, s consists only of lowercase letters.

Examples

Example 1

Input: s = "bcabc"

Output: "abc"

Example details omitted.

Example 2

Input: s = "cbacdcbc"

Output: "acdb"

Example details omitted.

Constraints

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

Solution Approach

Use a Stack to Build the Result

Initialize an empty stack and a frequency map of characters. Iterate through s, and for each character, pop stack elements that are greater than the current character if they appear later again. Push the current character if it's not already in the stack to maintain unique letters.

Greedy Lexicographical Choice

At each step, choose to remove letters from the stack only if a smaller letter can safely take their place later. This ensures the final string is the lexicographically smallest while still containing all unique letters exactly once.

Optimize Membership Checks

Maintain a set or bit-mask to track letters already in the stack to avoid duplicates. This avoids unnecessary stack pushes and guarantees O(n) time complexity since each letter is pushed and popped at most once.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(k) where k is the number of unique letters, to store the stack, frequency map, and membership tracking set.

What Interviewers Usually Probe

Watch if the candidate correctly handles repeated letters and maintains order.
Check if they can justify the greedy lexicographical choice at each stack operation.
Look for efficient membership tracking to prevent duplicate insertion into the stack.

Common Pitfalls or Variants

Common pitfalls

Pushing duplicates onto the stack instead of tracking existing letters.
Failing to pop characters when a smaller character appears later, leading to a non-optimal result.
Ignoring the last occurrence check, which can remove needed letters and break correctness.

Follow-up variants

Modify to allow uppercase letters and mixed case while still removing duplicates lexicographically.
Return the largest lexicographical order string instead of the smallest.
Apply the same stack-based approach to arrays of integers with unique selection constraints.

FAQ

What is the key pattern to solve Remove Duplicate Letters efficiently?

The key pattern is stack-based state management combined with greedy lexicographical choices, ensuring each letter is added once in the minimal order.

How does GhostInterview handle duplicate tracking?

It uses sets or bit-masks to monitor which characters are already in the stack, preventing duplicates and ensuring unique inclusion.

Why is popping from the stack necessary?

Popping allows replacing larger letters with smaller ones that appear later, maintaining the lexicographical minimality required by the problem.

What is the time complexity of the solution?

The algorithm runs in O(n) time since each character is pushed and popped at most once, with membership checks in O(1) using a set or bit-mask.

Can this method be applied to similar problems?

Yes, any problem requiring unique elements in optimal order with stack-based management or greedy selection can use the same approach.

terminal

Solution

Solution 1: Stack

We use an array `last` to record the last occurrence of each character, a stack to save the result string, and an array `vis` or an integer variable `mask` to record whether the current character is in the stack.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}
        stk = []
        vis = set()
        for i, c in enumerate(s):
            if c in vis:
                continue
            while stk and stk[-1] > c and last[stk[-1]] > i:
                vis.remove(stk.pop())
            stk.append(c)
            vis.add(c)
        return ''.join(stk)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}
        stk = []
        vis = set()
        for i, c in enumerate(s):
            if c in vis:
                continue
            while stk and stk[-1] > c and last[stk[-1]] > i:
                vis.remove(stk.pop())
            stk.append(c)
            vis.add(c)
        return ''.join(stk)

Continue Practicing

#402 remove k digits #1081 smallest subsequence of distinct characters #321 create maximum number