Question

316. 去除重复字母

English Version

题目描述

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成

 

注意：该题与 1081 https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters 相同

解法

方法一：栈

我们用一个数组 last 记录每个字符最后一次出现的位置，用栈来保存结果字符串，用一个数组 vis 或者一个整型变量 mask 记录当前字符是否在栈中。

遍历字符串 $s$，对于每个字符 $c$，如果 $c$ 不在栈中，我们就需要判断栈顶元素是否大于 $c$，如果大于 $c$，且栈顶元素在后面还会出现，我们就将栈顶元素弹出，将 $c$ 压入栈中。

最后将栈中元素拼接成字符串作为结果返回。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

class Solution:
  def removeDuplicateLetters(self, s: str) -> str:
    last = {c: i for i, c in enumerate(s)}
    stk = []
    vis = set()
    for i, c in enumerate(s):
      if c in vis:
        continue
      while stk and stk[-1] > c and last[stk[-1]] > i:
        vis.remove(stk.pop())
      stk.append(c)
      vis.add(c)
    return ''.join(stk)

class Solution {
  public String removeDuplicateLetters(String s) {
    int n = s.length();
    int[] last = new int[26];
    for (int i = 0; i < n; ++i) {
      last[s.charAt(i) - 'a'] = i;
    }
    Deque<Character> stk = new ArrayDeque<>();
    int mask = 0;
    for (int i = 0; i < n; ++i) {
      char c = s.charAt(i);
      if (((mask >> (c - 'a')) & 1) == 1) {
        continue;
      }
      while (!stk.isEmpty() && stk.peek() > c && last[stk.peek() - 'a'] > i) {
        mask ^= 1 << (stk.pop() - 'a');
      }
      stk.push(c);
      mask |= 1 << (c - 'a');
    }
    StringBuilder ans = new StringBuilder();
    for (char c : stk) {
      ans.append(c);
    }
    return ans.reverse().toString();
  }
}

class Solution {
public:
  string removeDuplicateLetters(string s) {
    int n = s.size();
    int last[26] = {0};
    for (int i = 0; i < n; ++i) {
      last[s[i] - 'a'] = i;
    }
    string ans;
    int mask = 0;
    for (int i = 0; i < n; ++i) {
      char c = s[i];
      if ((mask >> (c - 'a')) & 1) {
        continue;
      }
      while (!ans.empty() && ans.back() > c && last[ans.back() - 'a'] > i) {
        mask ^= 1 << (ans.back() - 'a');
        ans.pop_back();
      }
      ans.push_back(c);
      mask |= 1 << (c - 'a');
    }
    return ans;
  }
};

func removeDuplicateLetters(s string) string {
  last := make([]int, 26)
  for i, c := range s {
    last[c-'a'] = i
  }
  stk := []rune{}
  vis := make([]bool, 128)
  for i, c := range s {
    if vis[c] {
      continue
    }
    for len(stk) > 0 && stk[len(stk)-1] > c && last[stk[len(stk)-1]-'a'] > i {
      vis[stk[len(stk)-1]] = false
      stk = stk[:len(stk)-1]
    }
    stk = append(stk, c)
    vis[c] = true
  }
  return string(stk)
}

方法二

class Solution:
  def removeDuplicateLetters(self, s: str) -> str:
    count, in_stack = [0] * 128, [False] * 128
    stack = []
    for c in s:
      count[ord(c)] += 1
    for c in s:
      count[ord(c)] -= 1
      if in_stack[ord(c)]:
        continue
      while len(stack) and stack[-1] > c:
        peek = stack[-1]
        if count[ord(peek)] < 1:
          break
        in_stack[ord(peek)] = False
        stack.pop()
      stack.append(c)
      in_stack[ord(c)] = True
    return ''.join(stack)

func removeDuplicateLetters(s string) string {
  count, in_stack, stack := make([]int, 128), make([]bool, 128), make([]rune, 0)
  for _, c := range s {
    count[c] += 1
  }

  for _, c := range s {
    count[c] -= 1
    if in_stack[c] {
      continue
    }
    for len(stack) > 0 && stack[len(stack)-1] > c && count[stack[len(stack)-1]] > 0 {
      peek := stack[len(stack)-1]
      stack = stack[0 : len(stack)-1]
      in_stack[peek] = false
    }
    stack = append(stack, c)
    in_stack[c] = true
  }
  return string(stack)
}