##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1081.html

# 1081. Smallest Subsequence of Distinct Characters (Medium)

Return the lexicographically smallest subsequence of text that contains all the distinct characters of text exactly once.

Example 1:

Input: "cdadabcc"


Example 2:

Input: "abcd"
Output: "abcd"


Example 3:

Input: "ecbacba"
Output: "eacb"


Example 4:

Input: "leetcode"
Output: "letcod"


Note:

1. 1 <= text.length <= 1000
2. text consists of lowercase English letters.

## Solution 1.

• class Solution {
public String smallestSubsequence(String text) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
int length = text.length();
for (int i = 0; i < length; i++) {
char c = text.charAt(i);
map.put(c, i);
}
Set<Character> set = new HashSet<Character>();
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < length; i++) {
char c = text.charAt(i);
if (set.contains(c))
continue;
while (!stack.isEmpty() && stack.peek() > c) {
int lastIndex = map.get(stack.peek());
if (lastIndex > i) {
char prevC = stack.pop();
set.remove(prevC);
} else
break;
}
stack.push(c);
}
StringBuffer sb = new StringBuffer();
while (!stack.isEmpty())
sb.append(stack.pop());
sb.reverse();
return sb.toString();
}
}

############

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:
def smallestSubsequence(self, s: str) -> str:
last = defaultdict(int)
for i, c in enumerate(s):
last[c] = i
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)
return ''.join(stk)

############

# 1081. Smallest Subsequence of Distinct Characters
# https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

class Solution:
def smallestSubsequence(self, s: str) -> str:
counter, visited, stack = collections.Counter(s), set(), []

for c in s:
counter[c] -= 1
if c in visited: continue

while stack and stack[-1] > c and counter[stack[-1]] > 0:
visited.remove(stack.pop())

stack.append(c)

return "".join(stack)


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

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

• 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[] = [];
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
) {