316. 去除重复字母

参考316. 去除重复字母。

题目

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

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

解题思路

• 贪心+单调栈：字典序最小则尽量把小的排在前面,如果前面有比当前字符大的字符且后面还有该字符,则可以移除该字符。

贪心+单调栈

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] hash = new int[26];//计数
        for(char c : s.toCharArray()) hash[c-'a']++;
        //单调栈
        StringBuilder res = new StringBuilder();
        int[] set = new int[26];//可用boolean代替
        for(char c : s.toCharArray()) {
            hash[c-'a']--;
            if(set[c-'a'] == 1) continue;//c字符已存在栈中 直接舍弃
            while(res.length() > 0 && res.charAt(res.length()-1) > c && hash[res.charAt(res.length()-1)-'a'] > 0) {//移除大于的c的
                set[res.charAt(res.length()-1)-'a'] = 0;
                res.deleteCharAt(res.length()-1);
            }
            res.append(c);
            set[c-'a'] = 1;
        } 
        return res.toString();
    }

}

复杂度分析

• 时间复杂度：O(n)，n为字符串长度,计数n,遍历不超过2n。
• 空间复杂度：O(k)，计数哈希空间和栈空间都为k = 26,不超过字母种类数。