字典序最小的子序列

约定不等于承诺〃 2022-06-12 07:06 280阅读 0赞

给出一个由a-z组成的字符串S，求他的一个子序列，满足如下条件：

1、包含字符串中所有出现过的字符各1个。

2、是所有满足条件1的串中，字典序最小的。

例如：babbdcc，出现过的字符为：abcd，而包含abcd的所有子序列中，字典序最小的为abdc。

Input

输入1行字符串S，所有字符均为小写，字符串的长度为L。(1 <= L <= 100000)。

Output

输出包含S中所有出现过的字符，每个字符各1个，并且字典序最小的S的子序列。

Sample Input

babbdcc

Sample Output

abdc

利用双向队列：

#include <cstdio>
    #include <deque>
    #include <map>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int N =100001;
    int main()
    {
        int vis[26];
        char str[N];
        deque<char> deque1;
        map<char,int> map1;
        while(~scanf("%s",str))
        {
            deque1.clear();
            map1.clear();
            int len=strlen(str);
            for(int i=0; i<len; i++)
            {
                vis[str[i]-'a']=0;
                map1[str[i]]++;
            }
            for(int i=0;i<len;i++)
            {
                map1[str[i]]--;
                if(vis[str[i]-'a'])
                    continue;
                while(!deque1.empty()&&deque1.back()>str[i]&&map1[deque1.back()]>0)
                {
                    vis[deque1.back()-'a']=0;
                    //printf("c==%c ",deque1.back());
                    deque1.pop_back();
                }
               // printf("%c ",str[i]);
                deque1.push_back(str[i]);
                vis[str[i]-'a']=1;
            }
            while(!deque1.empty())
            {
                printf("%c",deque1.front());
                deque1.pop_front();
            }
            printf("\n");
        }
        return 0;
    }
     
    利用栈：

#include <cstdio>
    #include <iostream>
    #include <stack>
    #include <map>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int N =100001;
    int main()
    {
        int vis[26];
        char str[N];
        stack<char> queue1;
        map<char,int> map1;
        while(~scanf("%s",str))
        {
            while(!queue1.empty())
                queue1.pop();
            map1.clear();
            int len=strlen(str);
            for(int i=0; i<len; i++)
            {
                vis[str[i]-'a']=0;
                map1[str[i]]++;
            }
            for(int i=0;i<len;i++)
            {
                map1[str[i]]--;
                if(vis[str[i]-'a'])
                    continue;
                while(!queue1.empty()&&queue1.top()>str[i]&&map1[queue1.top()]>0)
                {
                    vis[queue1.top()-'a']=0;
                    //printf("c==%c ",deque1.back());
                    queue1.pop();
                }
                // printf("%c ",str[i]);
                queue1.push(str[i]);
                vis[str[i]-'a']=1;
            }
            string str1="";
            while(!queue1.empty())
            {
                str1=queue1.top()+str1;
                queue1.pop();
            }
            cout<<str1<<endl;
        }
        return 0;
    }