Description
给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件：原字符串中出现的字符，新字符串也必须包含。 新字符串中所有的字符均不相同。新字符串的字典序是满足上面两个条件的最小的字符串。
Input
多组输入：
仅一行，有一个只含有可打印字符的字符串 s。长度小于等于1e5
Output
在一行输出字典序最小的新字符串。
Sample Input Copy
4444555666
Sample Output Copy
456
HINT
字符串中包含空格
错误写法： 我一开始的思路即是将字符串排序后，用unique去重。显然是错误的。下面为一开始的错误代码。
#include<bits/stdc++.h> #include <iostream> using namespace std; #define ios ios::sync_with_stdio(false); int main() { char a[100020]; while(gets(a)) { vector<char> s(a,a+strlen(a)); vector<char>::iterator new_end; sort(s.begin(),s.end(),greater<char>()); new_end = unique(s.begin(),s.end()); s.erase(new_end,s.end()); while(!s.empty()) { cout<<s.back(); s.pop_back(); } cout<<'\n'; } return 0; }解题思路： 题意为在字符串的基础上保留一个每种出现的字符，并使保留下的字符串最小。（不能将字符串进行排序） 样例分析：
输入aaabbbb输出ab输入bbbbaaa输出ab输入aaabbaa输出ab输入bbaabbb输出ab #include<bits/stdc++.h> #include<algorithm> using namespace std; #define ios ios::sync_with_stdio(false); int vis[100020];//标记这个字符是否找过 int cnt[100020];//寻找最后一个字符 char s[100020]; int main() { deque <char> str; while(gets(s)) { memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); for(int i=0; i<strlen(s); i++) { vis[s[i]] = 1; cnt[s[i]]++; } for(int i=0; i<strlen(s); i++) { cnt[s[i]]--; if(vis[s[i]]==1) { vis[s[i]] = 0; while(!str.empty() && cnt[str.back()] > 0 && str.back() > s[i]) { vis[str.back()] = 1; str.pop_back(); } str.push_back(s[i]); } } while(!str.empty()) { cout<<str.front(); str.pop_front(); } cout<<'\n'; } return 0; }