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

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

All Problems

All Solutions