题目地址：https://ac.nowcoder.com/acm/contest/551/D

题目描述

CSL 以前不会字符串算法，经过一年的训练，他还是不会……于是他打算向你求助。
给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件： 

  • 原字符串中出现的字符，新字符串也必须包含。 
  • 新字符串中所有的字符均不相同。 
  • 新字符串的字典序是满足上面两个条件的最小的字符串。 

输入描述:

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

|s|≤105|s|≤105

输出描述:

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

示例1

输入

bab

输出

ab

示例2

输入

baca

输出

bac

备注:

ASCII字符集包含 94 个可打印字符(0x21 - 0x7E)，不包含空格。

解题思路：

若只考虑字符x 右边的 字符y的字典序是否比x的小来决策是否删除x，那么当删掉一个后又要重新考虑真个串，没有办法做，要转换思路。

因为要求字典序最小，所以每次遍历的时候都要从0x21 - 0x7E(33~127)一次遍历寻找可以作为结果的字符。（以这个为基础才保证了后面想法的正确性！）

last[]记录字符最后一次出现的位置，vis[]出现标注数组，ans[]标记字符是否已经作为答案，st为在字符串中寻找某个字符时的起始位置。

len记录字符串中出现不同字符的数目=答案的长度

第一层循环len次，每次都找出一个符合条件的字母作为答案。

第二层循环遍历[33,127]，对于一个满足vis[x]=1&&ans[x]=0的字符x，寻找它在指定范围内出现的位置i，

第三层循环遍历[33,127]，如果这个位置i之前存在最后出现的字符j（ans[j]=0）即last[j]<i则暂时不能把x作为结果。否则遍历完之后都没有找到ans[j]=0&&last[j]<i的，则说明i前面的字符都在i后面出现了或者i前面的字符（即使它的字典序比x小）都已经做了答案，且x的字典序是目前最小的，即把x作为答案，st=i+1,i（包括i）前面的字符都不用再考虑了。

举例：

i 0 1 2 3 4 5 6 7 8 9 10 11 12
s[i] c b c a c b e f e a c b c
last[s[i]]               ✅ ✅ ✅   ✅ ✅

 

把s[3]换成e试试看。手动模拟一下即可。

 

ac代码：

#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define  maxn 200//33~127
using namespace std;
typedef long long ll;
int vis[maxn]={0},ans[maxn]={0},last[maxn],len=0,st=0;
string s,res;
bool ok(int x)
{
    int t;
    for(t=st;t<s.length();t++)
        if(s[t]==(char)x)
            break;
    for(int j=33;j<=127;j++)
        if(vis[j]&&!ans[j]&&last[j]<t)
            return false;//在x之前出现了最后一次出现的字符，则暂时不将x作为答案
    st=t+1;//下次遍历从保留字母位置的下一个开始
    return true;//若x之前出现了last[j]>i的，又因为x的字典序是由贪心来的最小，所以i之前重复的字母都可删掉只保留x
}
char geta()
{
    int i;
    for(i=33;i<=127;i++)
        if(vis[i]&&!ans[i]&&ok(i))//出现过且答案中没有出现，且可以作为答案
        {
            ans[i]=1;
            break;
        }
     return char(i);
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    memset(last,-1,sizeof(last));
    cin>>s;
    //len=(int)s.length();
    for(int i=0;i<s.length();i++)
    {
        if(!vis[s[i]])
        {
            len++;
            vis[s[i]]=1;
        }
        last[s[i]]=i;
    }
    for(int i=0;i<len;i++)
        res+=geta();
     cout<<res<<endl;
    return 0;
}