CSL的字符串

时间：2024-12-26 15:03:38

链接：https://ac.nowcoder.com/acm/contest/551/D

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

CSL 以前不会字符串算法，经过一年的训练，他还是不会……于是他打算向你求助。
给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件：
  • 原字符串中出现的字符，新字符串也必须包含。
  • 新字符串中所有的字符均不相同。
  • 新字符串的字典序是满足上面两个条件的最小的字符串。

输入描述:

仅一行，有一个只含有可打印字符的字符串 s。
|s|≤10^5

输出描述:

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

示例1

输入

bab

输出

ab

示例2

输入

baca

输出

bac

备注:

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

对于字符串s，我们求出其每个字符最后出现的位置，用栈遍历s，对于第i个字符，如果栈顶字符大于这个字符并且栈顶字符最后出现的位置大于i就弹出栈顶字符并存入第i个字符，否则直接存入第i个字符，最后倒序输出栈内字符。

#include<iostream>

#include<cstring>

#include<map>

#include<stack>

using namespace std;

map<int,int>mp;

stack<char>st;

int v[];

int main()

{

    string s;

    cin>>s;

    for(int i=;i<s.size();i++)

    mp[s[i]]=i;

    st.push(s[]);

    v[s[]]=;

    for(int i=;i<s.size();i++)

    {

        if(v[s[i]])continue;

        while(!st.empty()&&st.top()>s[i]&&mp[st.top()]>i)

        {

            v[st.top()]=;

            st.pop();

        }

        st.push(s[i]);

        v[s[i]]=;

    }

    string a;

    while(!st.empty())

    {

        a+=st.top();

        st.pop();

    }

    for(int i=a.size()-;i>=;i--)

    cout<<a[i];

    cout<<endl;

    return ;

}

相关文章