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.
// OJ: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
// Time: O(N)
// Space: O(1)
class Solution {
public:
string smallestSubsequence(string text) {
int cnts[26] = {0}, used[26] = {0};
for (char c : text) ++cnts[c - 'a'];
string ans;
for (char c : text) {
cnts[c - 'a']--;
if (used[c - 'a']) continue;
while (ans.size() && cnts[ans.back() - 'a'] && c < ans.back()) {
used[ans.back() - 'a'] = 0;
ans.pop_back();
}
ans.push_back(c);
used[c - 'a'] = 1;
}
return ans;
}
};
Java
-
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(); } }
-
Todo
-
# 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)