Leetcode-316-去除重复字母

题目说明

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

示例 1：
输入：s = "bcabc"
输出："abc"

示例 2：
输入：s = "cbacdcbc"
输出："acdb"

提示：
1 <= s.length <= 104
s 由小写英文字母组成

题目分析

首先要知道什么叫 “字典序”。
字符串之间比较跟数字之间比较是不太一样的：字符串比较，是从头往后一个字符一个字符比较的，哪个字符串大取决于两个字符串中第一个对应不相等的字符。
所以，任意一个以 a 开头的字符串都大于任意一个以 b 开头的字符串。
为了得到最小字典序的结果，解题过程中，我们可以将最小的字符尽可能的放在前面，把前面出现的重复字母全部删除。这其实就是一个贪心策略。

方法一：贪心策略（逐个字符处理）

这种想法就是典型的贪心策略了：我们每次都找到当前能够移到最左边的、最小的字母。这就是我们得到结果的第一个字母，它之前的所有重复字母会被删掉；然后我们从它以后的字符串中，使用相同的逻辑，继续寻找第二个最小的字母。
所以，我们在代码实现上，可以使用递归。

代码实现：

public class RemoveDuplicateLetters {
    public String removeDuplicateLetters(String s) {
        if (s.length() == 0) 
        	return "";
        int position = 0;
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) < s.charAt(position)){
                boolean isReplaceable = true;
                for (int j = position; j < i; j++){
                    boolean isDuplicated = false;
                    for (int k = i; k < s.length(); k++){
                        if (s.charAt(k) == s.charAt(j)){
                            isDuplicated = true;
                            break;
                        }
                    }
                    isReplaceable = isReplaceable && isDuplicated;
                }

                if (isReplaceable){
                    position = i;
                }
            }
        }
        return s.charAt(position) 
+ removeDuplicateLetters0(
s.substring(position+1)
.replaceAll("" + s.charAt(position), ""));
    }
}

复杂度分析
时间复杂度：O(N^3)，因为用到了三重循环，最坏情况下时间复杂度达到了N^3。（超出运行时间限制）
空间复杂度：O(N)，每次给字符串切片都会创建一个新的字符串（字符串不可变），切片的数量受常数限制，最终复杂度为 O(N) * C = O(N)。

方法二：贪心策略改进

我们发现，对于“是否重复出现”的判断，每次都要偏离当前字母之后的所有字符，这显然做了很多重复工作。
优化的方法，我们可以用一个count数组，保存所有26个字母在s中出现的频次。当我们遍历字符串时，每遇到一个字母，就让它对应的count减一；当当前字母对应的count减为0时，说明之后不会再重复出现了，因此即使有更小的字母也不能替代它，我们直接就可以把它作为最左侧字母输出了。

public String removeDuplicateLetters(String s) {
        if (s.length() == 0) return "";
        int position = 0;
        // 定义一个count数组，用来保存26个字母在s中出现的频次
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++){
            count[s.charAt(i) - 'a'] ++; 
        }
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) < s.charAt(position)) {
                position = i; 
            }
            if (--count[s.charAt(i) - 'a'] == 0){
                break; 
            }
        }
        return s.charAt(position) + 
removeDuplicateLetters(s.substring(position+1)
.replaceAll("" + s.charAt(position), ""));
}

复杂度分析
时间复杂度：O(N)。每次递归调用占用 O(N) 时间。递归调用的次数受常数限制(只有26个字母)，最终复杂度为 O(N) * C = O(N)。

空间复杂度：O(N)，每次给字符串切片都会创建一个新的字符串（字符串不可变），切片的数量受常数限制，最终复杂度为 O(N) * C = O(N)。

方法三：贪心策略（用栈实现）

上面的方法由于递归的时候，用到了字符串切片的方法，导致必须要有线性的空间复杂度，而且运行时间也并不短。那还没有别的优化方法呢？
这就需要结合其它的数据结构了。我们可以用栈来存储最终返回的字符串。

代码实现如下：

public String removeDuplicateLetters(String s) {
    Stack<Character> stack = new Stack<>();
    HashSet<Character> seen = new HashSet<>();
    HashMap<Character, Integer> last_occur = new HashMap<>();
    for (int i = 0; i < s.length(); i++){
        last_occur.put(s.charAt(i), i); 
    }
    // 遍历字符串，判断是否入栈
    for (int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if (!seen.contains(c)){
            while (!stack.isEmpty() &&
                    c < stack.peek() &&
                    last_occur.get(stack.peek()) > i){
                seen.remove(stack.pop());
            }
            seen.add(c);
            stack.push(c);
        }
    }
    // 将栈中元素保存成字符串输出
    StringBuilder sb = new StringBuilder(stack.size());
    for (Character c: stack){
        sb.append(c.charValue());
    }
    return sb.toString();
}

复杂度分析
时间复杂度：O(N)。虽然看起来是双重循环，但内循环的次数受栈中剩余字符总数的限制，因为栈中的元素不重复，不会超出字母表大小，因此最终复杂度仍为 O(N)。
空间复杂度：O(1)。看上去空间复杂度像是 O(N)，但实际上并不是。首先，seen 中字符不重复，其大小会受字母表大小的限制，所以是O(1)。其次，只有 stack 中不存在的元素才会被压入，因此 stack 中的元素也唯一。所以最终空间复杂度为 O(1)。

方法四

其实通过栈还有更加容易理解的解题思路，具体代码如下

class Solution {
    public String removeDuplicateLetters(String s) {
            Stack<Character> stack = new Stack<>();
            
            for(int i =0;i<s.length();i++){
                char c = s.charAt(i);
                if(stack.contains(c)){
                    continue;
                }
                //栈不为空，并且 当前字母比栈中字母更小，并且从当前位置开始往后还有栈中的字母存在，那么就弹出
                while(!stack.isEmpty()&& c<stack.peek()&& s.indexOf(stack.peek(),i)!=-1){
                    stack.pop();
                }
                stack.push(c);
            }
            char[] charArr = new char[stack.size()];
            for(int i=0;i<stack.size();i++){
                charArr[i] = stack.get(i);
            }
            return new String(charArr);
    }
}