[LeetCode] 316. Remove Duplicate Letters

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.

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

Example 1:

Input: s = "cdadabcc"
Output: "adbc"

Example 2:

Input: s = "abcd"
Output: "abcd"

Example 3:

Input: s = "ecbacba"
Output: "eacb"

Example 4:

Input: s = "leetcode"
Output: "letcod"

Constraints:

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

去除重复字母。

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

思路是单调栈。这道题的单调栈里面，字母序是降序的，也就是说栈顶元素的字典序是最小的，栈的底部的字母的字典序是最大的。首先我们需要用一个map记录每个字母都出现过几次，同时需要一个hashset（seen）记录最后拼接起来的字符串中有没有出现过相同字母，还需要一个stack帮助比较每个字母之间的字典序，决定字母的取舍。

第一次遍历input字符串，用hashmap把每个不同字符的出现次数记录下来。再次遍历input字符串，每遍历到一个字符，你需要做如下几个动作

去hashmap中对其出现次数 - 1
如果这个字符已经被放入最后拼接的结果中了，则跳过不处理
接下来用一个while循环判断如下内容：如果stack不为空，且栈顶字母的字典序比当前字母的字典序更大，同时hashmap中栈顶字母的出现次数没有用完，则把栈顶字母弹出
- 这里的逻辑是如果栈顶字母字典序大但是还未用完，我们就可以弹出，否则就不能弹出，保持原顺序
把当前字符入栈并在hashset中记录一下，说明在output中已经有过这个字母了

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public String removeDuplicateLetters(String s) {
 3         int[] count = new int[26];
 4         for (int i = 0; i < s.length(); i++) {
 5             count[s.charAt(i) - 'a']++;
 6         }
 7 
 8         Stack<Character> stack = new Stack<>();
 9         boolean[] seen = new boolean[26];
10         for (int i = 0; i < s.length(); i++) {
11             count[s.charAt(i) - 'a']--;
12             // 如果当前这个字母已经存入过结果集中，则跳过
13             if (seen[s.charAt(i) - 'a']) {
14                 continue;
15             }
16             // 如果当前stack不为空，当前字母字典序更小，且栈顶元素之后还会遇见，则开始弹出操作
17             // 这样确保字典序小的字母一直先入栈
18             while (!stack.isEmpty() && s.charAt(i) < stack.peek() && count[stack.peek() - 'a'] > 0) {
19                 seen[stack.peek() - 'a'] = false;
20                 stack.pop();
21             }
22             stack.push(s.charAt(i));
23             seen[s.charAt(i) - 'a'] = true;
24         }
25 
26         // 将字符从stack中弹出，构造成最后的结果
27         StringBuilder sb = new StringBuilder();
28         while (!stack.isEmpty()) {
29             sb.append(stack.pop());
30         }
31         return sb.reverse().toString();
32     }
33 }