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         // corner case
 4         if (s == null || s.length() == 0) {
 5             return null;
 6         }
 7 
 8         // normal case
 9         int[] count = new int[26];
10         for (int i = 0; i < s.length(); i++) {
11             count[s.charAt(i) - 'a']++;
12         }
13 
14         Stack<Character> stack = new Stack<>();
15         boolean[] seen = new boolean[26];
16         for (int i = 0; i < s.length(); i++) {
17             count[s.charAt(i) - 'a']--;
18             if (seen[s.charAt(i) - 'a']) {
19                 continue;
20             }
21             while (!stack.isEmpty() && stack.peek() > s.charAt(i) && count[stack.peek() - 'a'] > 0) {
22                 seen[stack.peek() - 'a'] = false;
23                 stack.pop();
24             }
25             stack.push(s.charAt(i));
26             seen[s.charAt(i) - 'a'] = true;
27         }
28         StringBuilder sb = new StringBuilder();
29         for (char c : stack) {
30             sb.append(c);
31         }
32         return sb.toString();
33     }
34 }

 

LeetCode 题目总结