Question

1081. Smallest Subsequence of Distinct Characters

中文文档

Description

Given a string s, return _the __lexicographically smallest_ _subsequence__ of_ s _that contains all the distinct characters of_ s _exactly once_.

 

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

 

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

 

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Solutions

Solution 1

class Solution:
  def smallestSubsequence(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 smallestSubsequence(String text) {
    int[] cnt = new int[26];
    for (char c : text.toCharArray()) {
      ++cnt[c - 'a'];
    }
    boolean[] vis = new boolean[26];
    char[] cs = new char[text.length()];
    int top = -1;
    for (char c : text.toCharArray()) {
      --cnt[c - 'a'];
      if (!vis[c - 'a']) {
        while (top >= 0 && c < cs[top] && cnt[cs[top] - 'a'] > 0) {
          vis[cs[top--] - 'a'] = false;
        }
        cs[++top] = c;
        vis[c - 'a'] = true;
      }
    }
    return String.valueOf(cs, 0, top + 1);
  }
}

class Solution {
public:
  string smallestSubsequence(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 smallestSubsequence(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)
}

function smallestSubsequence(s: string): string {
  const f = (c: string): number => c.charCodeAt(0) - 'a'.charCodeAt(0);
  const last: number[] = new Array(26).fill(0);
  for (const [i, c] of [...s].entries()) {
    last[f(c)] = i;
  }
  const stk: string[] = [];
  let mask = 0;
  for (const [i, c] of [...s].entries()) {
    const x = f(c);
    if ((mask >> x) & 1) {
      continue;
    }
    while (stk.length && stk[stk.length - 1] > c && last[f(stk[stk.length - 1])] > i) {
      mask ^= 1 << f(stk.pop()!);
    }
    stk.push(c);
    mask |= 1 << x;
  }
  return stk.join('');
}

Solution 2

class Solution {
  public String smallestSubsequence(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();
  }
}