leet code 316. 去除重复字母

316. 去除重复字母

题目描述

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

示例 1：

输入：s = "bcabc" 输出："abc"

示例 2：

输入：s = "cbacdcbc" 输出："acdb"

提示：

• 
• s 由小写英文字母组成

题目解析

• 考虑从前往后遍历或者从后往前遍历
• 题目要求需要保证字典序不变
• 那么最终的输出结果中的每一个字符，需要考虑和全局的关系
• 以 字符串 s = "cbacdcbc" 为例

• 遍历到字符 c，记结果集为 ans = c
• 遍历到字符 b，很显然 b < c 并且没有遍历到的字符中，还存在有 c

• 所以删除 c, ans = b

• 遍历到字符a, a < b同理删除b,ans = a
• 遍历到字符c, c > a, --> ans = ac
• ...................d, d > c, --> ans = acd
• ...................c, ans = acd,字符c已经存在跳过
• ...................b, b < d,后续没有 b 了,---> ans = acdb
• ...................c,跳过，最终 ans = acdb

• 所以需要预统计字符串s中各个字符出现的次数

show code

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        // 统计 s 中各个字符各多少个
        for (int i = 0; i < n; i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        // 用于标记结果集合中已经添加的字符
        boolean[] sign = new boolean[26];


        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char at = s.charAt(i);
            cnt[at - 'a']--;
            // 重复的字符直接跳过
            if(sign[at - 'a']) {
                continue;
            }
            // 以 c b 为例，遍历到字符 b; b < c  并且后续还有字符 c 
            // 判断条件：结果集中存在有值 且 at < 结果集中的最后一个字符，且该字符在右边还有
            while(ans.length() > 0 && at < ans.charAt(ans.length() - 1) && cnt[ans.charAt(ans.length() - 1) - 'a'] > 0) {
                // 移除 标记
                sign[ans.charAt(ans.length() - 1) - 'a'] = false;
                // 移除 c
                ans.deleteCharAt(ans.length() - 1);
            }
            ans.append(at);
            // 标记
            sign[at - 'a'] = true;
        }
        return ans.toString();
    }
}

参考

https://leetcode.cn/problems/remove-duplicate-letters/solutions/2381483/gen-zhao-wo-guo-yi-bian-shi-li-2ni-jiu-m-zd6u/