Problem
给出一个由a-z组成的字符串S,求他的一个子序列,满足如下条件:
1、包含字符串中所有出现过的字符各1个。
2、是所有满足条件1的串中,字典序最小的。
例如:babbdcc,出现过的字符为:abcd,而包含abcd的所有子序列中,字典序最小的为abdc。
Solution
一个栈,当前没有在栈内,栈顶不是最后一个,且当前更小,就出1个入1个。
Code
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| #include<iostream> #include<stdio.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cstring> #include<stack>
#define mem(ss) memset(ss,0,sizeof(ss)) #define rep(d, s, t) for(int d=s;d<=t;d++) #define rev(d, s, t) for(int d=s;d>=t;d--) typedef long long ll; typedef long double ld; typedef double db; const ll mod = 998244353; const int N = 1e4 + 10; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
inline ll read() { ll data = 0; char ch = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar(); return data; } stack<char>s; int len; char x[100020]; bool f[30]; int las[30]; char ans[30]; int main() { scanf("%s",x); len=strlen(x); for(int i=0;i<len;i++){ las[x[i]-'a']=i; } for(int i=0;i<len;i++){ while(!s.empty()&&x[i]<s.top()&&las[s.top()-'a']>i&&!f[x[i]-'a']){ f[s.top()-'a']=false; s.pop();
} if(!f[x[i]-'a']){ s.push(x[i]); f[x[i]-'a']=true; } } int t=0; while(!s.empty()){ ans[++t]=s.top(); s.pop(); } for(int i=t;i>=1;i--){ printf("%c",ans[i]); } return 0; }
|