“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 D.CSL 的字符串

“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 D.CSL 的字符串

“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 D.CSL 的字符串

题目描述

CSL 以前不会字符串算法，经过一年的训练，他还是不会……于是他打算向你求助。

给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件：
原字符串中出现的字符，新字符串也必须包含。
新字符串中所有的字符均不相同。
新字符串的字典序是满足上面两个条件的最小的字符串。

输入描述:

仅一行，有一个只含有可打印字符的字符串 s。

∣ s ∣ ≤ 1 0 5 |s| leq 10 ^ 5 ∣s∣≤105

输出描述:

在一行输出字典序最小的新字符串。

示例1

输入

bab

输出

ab

示例2

输入

baca

输出

bac

记录每个字符出现的次数，模拟栈操作即可，AC代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;int vis[N],num[N];
int main(){string s;cin>>s;string ans="";for(int i=0;i<s.length();i++){num[s[i]]++;}for(int i=0;i<s.length();i++){num[s[i]]--;if(vis[s[i]]) continue;while(num[ans.back()] && s[i]<ans.back()){vis[ans.back()]=0;ans.pop_back();}ans+=s[i];vis[s[i]]=1;}cout<<ans<<endl;return 0;
}