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"
Output: "adbc"

Example 2:

Input: "abcd"
Output: "abcd"

Example 3:

Input: "ecbacba"
Output: "eacb"

Example 4:

Input: "leetcode"
Output: "letcod"

Note:

1 <= text.length <= 1000
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;
            }
            set.add(c);
            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)
            vis.add(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())
            
            visited.add(c)
            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;
        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;
    }
};

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

1081 - Smallest Subsequence of Distinct Characters

1081. Smallest Subsequence of Distinct Characters (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1081. Smallest Subsequence of Distinct Characters (Medium)

Solution 1.

All Problems

All Solutions