# Remove Duplicate Letters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-duplicate-letters)
Canonical: https://scaleengineer.com/dsa/problems/remove-duplicate-letters
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack, Monotonic Stack
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [DRW](https://scaleengineer.com/companies/drw), [FactSet](https://scaleengineer.com/companies/factset)
---
## Problem
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 <= 104`
* `s` consists of lowercase English letters.

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

# Approaches
## Brute Force - Generate All Subsequences
This approach generates all possible subsequences that contain each character exactly once, then finds the lexicographically smallest one among them.
**Time:** O(2^n * n) where n is the length of string - exponential time due to generating all subsequences · **Space:** O(2^n * n) for storing all possible subsequences
**Pros:** Simple to understand and implement; Guaranteed to find the correct answer; No complex data structures required
**Cons:** Extremely inefficient for large inputs; Exponential time and space complexity; Not practical for real-world applications; Will cause timeout for most test cases
### Explanation
The brute force approach involves generating all possible subsequences of the string that contain each unique character exactly once. For each subsequence, we check if it contains all unique characters from the original string exactly once. Among all valid subsequences, we return the lexicographically smallest one.

```java
public String removeDuplicateLetters(String s) {
    Set<Character> uniqueChars = new HashSet<>();
    for (char c : s.toCharArray()) {
        uniqueChars.add(c);
    }
    
    List<String> validSubsequences = new ArrayList<>();
    generateSubsequences(s, 0, new StringBuilder(), uniqueChars, validSubsequences);
    
    Collections.sort(validSubsequences);
    return validSubsequences.get(0);
}

private void generateSubsequences(String s, int index, StringBuilder current, 
                                Set<Character> required, List<String> result) {
    if (index == s.length()) {
        if (current.length() == required.size() && 
            containsAllRequired(current.toString(), required)) {
            result.add(current.toString());
        }
        return;
    }
    
    // Include current character
    current.append(s.charAt(index));
    generateSubsequences(s, index + 1, current, required, result);
    current.deleteCharAt(current.length() - 1);
    
    // Exclude current character
    generateSubsequences(s, index + 1, current, required, result);
}
```
### Algorithm
1. Find all unique characters in the string
2. Generate all possible subsequences using recursion
3. Filter subsequences that contain each unique character exactly once
4. Sort all valid subsequences lexicographically
5. Return the first (smallest) subsequence

## Greedy with Stack (Optimal Solution)
This approach uses a stack-based greedy algorithm to build the lexicographically smallest result by making optimal local decisions.
**Time:** O(n) where n is the length of string - each character is pushed and popped at most once · **Space:** O(1) or O(26) for the arrays and stack, which is constant space
**Pros:** Optimal time and space complexity; Elegant greedy approach; Single pass through the string; Uses efficient data structures
**Cons:** Requires understanding of greedy algorithms; Logic for when to remove characters can be tricky to grasp; Need to carefully track character frequencies and inclusion status
### Explanation
The optimal approach uses a stack to build the result string while ensuring lexicographical order. We iterate through the string and for each character, we decide whether to include it immediately or wait for a better position. The key insight is that we can remove a character from our current result if:
1. The current character is smaller than the last character in our result
2. The last character appears later in the string
3. The last character is not already in our final result

```java
public String removeDuplicateLetters(String s) {
    // Count frequency of each character
    int[] count = new int[26];
    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }
    
    // Track which characters are already in result
    boolean[] inResult = new boolean[26];
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        // Decrease count as we process the character
        count[c - 'a']--;
        
        // If character is already in result, skip it
        if (inResult[c - 'a']) {
            continue;
        }
        
        // Remove characters from stack if:
        // 1. Current char is smaller than stack top
        // 2. Stack top appears later in string (count > 0)
        while (!stack.isEmpty() && 
               c < stack.peek() && 
               count[stack.peek() - 'a'] > 0) {
            char removed = stack.pop();
            inResult[removed - 'a'] = false;
        }
        
        // Add current character to result
        stack.push(c);
        inResult[c - 'a'] = true;
    }
    
    // Build result string from stack
    StringBuilder result = new StringBuilder();
    for (char c : stack) {
        result.append(c);
    }
    
    return result.toString();
}
```
### Algorithm
1. Count frequency of each character in the string
2. Use a stack to build the result and a boolean array to track included characters
3. For each character in the string:
   - Decrease its count
   - Skip if already included in result
   - Remove characters from stack top if current char is smaller and removed char appears later
   - Add current character to stack and mark as included
4. Convert stack to string and return

# Solutions
### Java

```java
class Solution {
public
  String removeDuplicateLetters(String s) {
    int n = s.length();
    int[] last = new int[26];
    for (int i = 0; i < n; ++i) {
      last[s.charAt(i) - 'a'] = i;
    }
    Deque<Character> stk = new ArrayDeque<>();
    int mask = 0;
    for (int i = 0; i < n; ++i) {
      char c = s.charAt(i);
      if (((mask >> (c - 'a')) & 1) == 1) {
        continue;
      }
      while (!stk.isEmpty() && stk.peek() > c && last[stk.peek() - 'a'] > i) {
        mask ^= 1 << (stk.pop() - 'a');
      }
      stk.push(c);
      mask |= 1 << (c - 'a');
    }
    StringBuilder ans = new StringBuilder();
    for (char c : stk) {
      ans.append(c);
    }
    return ans.reverse().toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string removeDuplicateLetters(string s) {
    int n = s.size();
    int last[26] = {0};
    for (int i = 0; i < n; ++i) {
      last[s[i] - 'a'] = i;
    }
    string ans;
    int mask = 0;
    for (int i = 0; i < n; ++i) {
      char c = s[i];
      if ((mask >> (c - 'a')) & 1) {
        continue;
      }
      while (!ans.empty() && ans.back() > c && last[ans.back() - 'a'] > i) {
        mask ^= 1 << (ans.back() - 'a');
        ans.pop_back();
      }
      ans.push_back(c);
      mask |= 1 << (c - 'a');
    }
    return ans;
  }
};

```

### Python

```python
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)

```