去除重复字母

题目链接

去除重复字母

题目描述

注意点

• s 由小写英文字母组成
• 1 <= s.length <= 10^4
• 需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）

解答思路

• 本题与移掉 K 位数字类似，需要注意的是，并不是每个字母都能被移除，而是要移除重复字母，保证字符串中每个字母都只出现了一次
• 又因为要保证结果的字典序最小，要尽可能保证前面的字母更小，所以要尽可能保证字符串是严格递增的（没办法保证一定递增，部分字母不重复无法去除）
• 对于任意一个位置处的字母ch，有以下几种情况：
  • 如果ch已经加入到结果中，因为字母不能重复，则不会继续加入到结果中
  • 如果ch还未加入到结果中，且此时结果末尾处的字母小于ch，则直接将ch加入到结果中
  • 如果ch还未加入到结果中，且此时结果末尾处的字母大于ch，且剩余字符串中已经没有末尾处的字母，则不能弹出末尾字母（保证末尾字母有出现在结果中），直接将ch加入到结果中
  • 如果ch还未加入到结果中，且此时结果末尾处的字母大于ch，且剩余字符串中还有末尾处的字母，则需要弹出末尾字母，直到满足上面两个要求为止，再将ch加入到结果中

代码

class Solution {
    public String removeDuplicateLetters(String s) {
        // 存储到某个位置时剩余字符串中每个小写字母的数量
        int[] arr = new int[26];
        // 存储每个小写字母是否已经添加到结果集中
        boolean[] visited = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            arr[s.charAt(i) - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 该字母如果已经加入到结果中，不能重复，则不做考虑
            if (visited[ch - 'a']) {
                arr[ch - 'a']--;
                continue;
            }
            // 末尾字母大于c，且后方还有末尾字母，则弹出末尾字母
            while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch && arr[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                visited[sb.charAt(sb.length() - 1) - 'a'] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
            sb.append(ch);
            visited[ch - 'a'] = true;
            arr[ch - 'a']--;
        }
        return sb.toString();
    }
}

关键点

• 怎么保证结果的字典序最小
• 怎么保证原有字符串中的字母在结果中都出现且只出现了一次