1081. Smallest Subsequence of Distinct Characters
Return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.
Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/
- new solution update 2022.02.11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
string smallestSubsequence(string s) {
int arr[26]{0,};
int contain = 0;
for(auto& ch : s) ++arr[ch-'a'];
string res;
for(auto& ch : s) {
while(!res.empty() && res.back() > ch && arr[res.back() - 'a'] && !(contain & (1<<(ch-'a')))) {
contain ^= (1<<(res.back()-'a'));
res.pop_back();
}
--arr[ch-'a'];
if(!(contain & (1<<(ch-'a')))) {
res += ch;
contain |= (1<<(ch-'a'));
}
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
string dfs(map<char,list<int>> &m, set<char>& letter, int pos) {
if(letter.empty()) {
return "";
}
for(char ch : letter) {
bool flag = true;
int npos = *upper_bound(m[ch].begin(), m[ch].end(), pos);
for(char other : letter) {
if(m[other].back() < npos) {
flag = false;
break;
}
}
if(flag) {
letter.erase(ch);
return ch + dfs(m, letter, npos);
}
}
return "";
}
public:
string smallestSubsequence(string s) {
map<char,list<int>> m;
set<char> letter;
for(int i = 0; i < s.length(); i++) {
letter.insert(s[i]);
m[s[i]].push_back(i);
}
return dfs(m, letter, -1);
}
};
|
