> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0316-remove-duplicate-letters.md).

# 0316. Remove Duplicate Letters

<https://leetcode.com/problems/remove-duplicate-letters>

## Description

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/>

## ac

```java
class Solution {
    public String removeDuplicateLetters(String s) {
        // edge cases
        if (s.length() <= 1) return s;

        int n = s.length();
        int[] cnts = new int[26];
        for (char c : s.toCharArray()) {
            cnts[c - 'a']++;
        }
        boolean[] onStack = new boolean[26];
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            cnts[c - 'a']--;
            if (onStack[c - 'a']) {
                continue; // skip
            }
            while (!stack.isEmpty() && c < stack.peek() && cnts[stack.peek() - 'a'] > 0) {
                onStack[stack.pop() - 'a'] = false;
            }
            stack.push(c);
            onStack[c - 'a'] = true;
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        return sb.reverse().toString();
    }
}

/*
stack, walk string, if meet smaller char and old char has more later, pop old.
*/
```