去除重复字母

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

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 10⁴
s 由小写英文字母组成

方法一：一个字符一个字符处理

每次递归中，在保证其他字符至少出现一次的情况下，确定最小左侧字符。之后再将未处理的后缀字符串继续递归

public String removeDuplicateLetters(String s) {
    if (s.equals("")) {
        return "";
    }
    int[] map = new int[26];
    for (int i = 0; i < s.length(); i++) {
        map[s.charAt(i) - 'a']++;
    }
    int pos = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) < s.charAt(pos)) {
            pos = i;
        }
        // 等于0表示之后不会再出现了，但是之前的字符后面肯定会在出现
        if (--map[s.charAt(i) - 'a'] == 0) {
            break;
        }
    }
    // 当前最左侧的应该是保留最小的元素，然后将字符串中的这个字符去除，这里做截取是将这个位置前面的元素去除（因为当前位置才是最小的元素）
    return s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll(s.charAt(pos) + "", ""));
}

时间复杂度：O(N)，每次递归调用占用 O(N)递归调用的次数受常数限制(只有26个字母，每次都会去除重复的字母)，最终复杂度为 O(N) * C = O(N)∗C=O(N)
空间复杂度：O(N)，每次给字符串切片都会创建一个新的字符串，切片的数量受常数限制，最终复杂度为 O(N)

方法二：用栈
用栈来存储最终返回的字符串，并维持字符串的最小字典序
每遇到一个字符，如果这个字符不存在于栈中，就需要将该字符压入栈中。但在压入之前，需要先将之后还会出现，并且字典序比当前字符大的栈顶字符移除，然后再将当前字符压入

public String removeDuplicateLetters(String s) {
    // 存储栈中存在的元素
    Set<Character> set = new HashSet<>();
    // 记录字符在数组中最后出现的位置
    Map<Character, Integer> map = new HashMap<>();
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        map.put(s.charAt(i), i);
    }
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // 如果当前元素已经在栈中就不考虑了（即重复）
        if (!set.contains(c)) {
            // 将之后还会出现且比当前元素大的从栈顶弹出
            while (!stack.isEmpty() && stack.peek() > c && map.get(stack.peek()) > i) {
                set.remove(stack.pop());
            }
            stack.push(c);
            set.add(c);
        }
    }
    StringBuilder sb = new StringBuilder(stack.size());
    for (Character c : stack) {
        sb.append(c.charValue());
    }
    return sb.toString();
}

时间复杂度：O(N)虽然外循环里面还有一个内循环，但内循环的次数受栈中剩余字符总数的限制（由于不重复，最多26个），因此最终复杂度仍为 O(N)
空间复杂度：O(1)，由于不重复，最多26个

最后编辑于：2024.04.28 05:46:34