LeetCode316-去除重复字母

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/remove-duplicate-letters/

中文链接：https://leetcode-cn.com/problems/remove-duplicate-letters/

题目详述

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

示例 1:

1
2
输入: "bcabc"
输出: "abc"

示例 2:

1
2
输入: "cbacdcbc"
输出: "acdb"

题目详解

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_00316 {

    public String removeDuplicateLetters(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            last[s.charAt(i) - 'a'] = i;
        }
        boolean[] vis = new boolean[26];
        char[] cs = new char[s.length()];
        int top = -1;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (!vis[c - 'a']) {
                while (top >= 0 && c < cs[top] && i < last[cs[top] - 'a']) {
                    vis[cs[top--] - 'a'] = false;
                }
                cs[++top] = c;
                vis[c - 'a'] = true;
            }
        }
        return String.valueOf(cs, 0, top + 1);
    }
}