> For the complete documentation index, see [llms.txt](https://luj.gitbook.io/code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://luj.gitbook.io/code/advanced-data-structures/3-monotone-stack/remove-duplicate-letters.md).

# Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

## Example

**Example 1:**

```
Input: "bcabc"
Output: "abc"
```

**Example 2:**

```
Input: "cbacdcbc"
Output: "acdb"
```

## Note

维护一个严格单调递增的栈，栈内元素唯一。同时维护一个counting map

遍历元素，对于栈：

* 遇到栈内出现的元素，跳过
* 遇到栈顶元素比当前元素大的，根据counting map的情况进行pop（贪心法则：不是唯一的，那么我们到后面再去加它）

遍历元素，对于counting map：

* 更新其出现的counting

## Code

```java
class Solution {
    public String removeDuplicateLetters(String S) {
        Stack<Character> s = new Stack<>();
        Set<Character> visited = new HashSet<>();
        int[] set = new int[26];
        for (char c : S.toCharArray()) {
            set[c - 'a']++;    
        }

        for (char c : S.toCharArray()) {
            set[c - 'a']--;
            if (visited.contains(c)) { continue; }
            while (!s.isEmpty() && c < s.peek() && set[s.peek() - 'a'] != 0) {
                visited.remove(s.pop());
            }
            s.push(c);
            visited.add(c);
        }

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

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luj.gitbook.io/code/advanced-data-structures/3-monotone-stack/remove-duplicate-letters.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.