Welcome to Subscribe On Youtube

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

Stack

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  };
  

• 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)
  
  

• 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('');
  }
  
  

All Problems

All Solutions