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

Solution 1

Stack

Solution 2

This implementation uses breadth-first search, followed by monotonic stack, followed by bit manipulation. It traverses the relevant values and updates its state as each value is processed. The auxiliary container determines which pending state is processed next. After all required states have been considered, the maintained result is returned.

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

• 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