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