LeetCode1081-不同字符的最小子序列

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

中文链接：https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/

题目详述

返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。

示例 1：

1
2
输入："cdadabcc"
输出："adbc"

示例 2：

1
2
输入："abcd"
输出："abcd"

示例 3：

1
2
输入："ecbacba"
输出："eacb"

示例 4：

1
2
输入："leetcode"
输出："letcod"

提示：

  • 1 <= text.length <= 1000
  • text 由小写英文字母组成

题目详解

  • 首先统计各个字符出现的次数。
  • 维护一个单调栈，从栈底到栈顶单调递增。
  • 遍历字符串，对于每一个字符，首先让它的出现次数递减。如果这个字符在之前出现过，直接跳过；否则如果它比栈顶字符小，并且后面还存在这个字符，弹出栈顶并设置出现标志为 false，最后把当前字符入栈并设置出现标志。
  • 最终栈中剩余的字符组合的字符串就是结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_01081 {

    public String smallestSubsequence(String text) {
        int[] cnt = new int[26];
        for (char c : text.toCharArray()) {
            ++cnt[c - 'a'];
        }
        boolean[] vis = new boolean[26];
        char[] cs = new char[text.length()];
        int top = -1;
        for (char c : text.toCharArray()) {
            --cnt[c - 'a'];
            if (!vis[c - 'a']) {
                while (top >= 0 && c < cs[top] && cnt[cs[top] - 'a'] > 0) {
                    vis[cs[top--] - 'a'] = false;
                }
                cs[++top] = c;
                vis[c - 'a'] = true;
            }
        }
        return String.valueOf(cs, 0, top + 1);
    }
}
  • 因为只需判断后面是否存在该字符，所以可以不用统计字符出现次数，转而计算每个字符最后出现的位置，这样判断是否为最后一个字符就很简单了。
  • 因为只需要 26 个标志位，可以使用位运算压缩，不过看上去不那么直观。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_01081 {

    public String smallestSubsequence(String text) {
        int[] last = new int[26];
        for (int i = 0; i < text.length(); ++i) {
            last[text.charAt(i) - 'a'] = i;
        }
        char[] cs = new char[text.length()];
        int top = -1;
        int vis = 0;
        for (int i = 0; i < text.length(); ++i) {
            char c = text.charAt(i);
            if ((vis & (1 << (c - 'a'))) == 0) {
                while (top >= 0 && c < cs[top] && i < last[cs[top] - 'a']) {
                    vis &= ~(1 << (cs[top--] - 'a'));
                }
                cs[++top] = c;
                vis |= 1 << (c - 'a');
            }
        }
        return String.valueOf(cs, 0, top + 1);
    }
}