这道题目和1081. Smallest Subsequence of Distinct Characters是同一道题目,解题方法如下:
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> dict(256, 0);
vector<bool> visited(256, false);
for(auto ch : s) dict[ch]++;
string result = "0";
/** the key idea is to keep a monotically increasing sequence **/
for(auto c:s)
{
dict[c]--;
if(visited[c]) continue;
while(c < result.back() && dict[result.back()])
{
visited[result.back()] = false;
result.pop_back();
}
result += c;
visited[c] = true;
}
return result.substr(1);
}
};
这里最开始拿到题目,一时间无从下手,直到看到评论区大神的解法,这里巧妙计算每个字母出现的频率,当某个字母后面还有,并且字符序列小于当前序列,那么就从当前结果中pop出去。