【题意】给定长度为n(<=2*10^5)的字符串，求最短的字典序最小的非子序列字符串。

【算法】字符串DP

【题解】

先考虑计算最短长度，再考虑求字典序最小。

关键在于发掘出【最短的非子序列字符串】具有最优子结构，定义f(s)为字符串s的最短的非子序列字符串长度，假设最短的非子序列字符串为t，当t的第一个字母是c（任意字母）时，只有两种情况：

①s中无c，f(s)=1最短。

②对于s中最左边位置p的c，f(s)=f(s.suffix(p+1))+1，最后这个+1就是c。

很熟悉对吗？①是终止条件，②是状态转移，满足最优子结构性质，当确定第一个字母后，剩余部分可以转化为计算完毕的子问题。

那么正式定义状态转移方程，令f[i]表示字符串的后缀i的最短非子序列字符串的长度，pos[i][j]表示从位置i开始第一个字母j出现的位置。

状态转移方程：f[i]=min(f[pos[i][j]+1])+1，0<=j<26。

最后要求字典序最小，从f[0]开始对于每一步找到最小的字母c满足f[i]==f[pos[i][c]]+1输出即可。

复杂度O(n*26)。

考虑清楚边界问题！

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=200010;int f[maxn],pos[maxn][30],n;char s[maxn];int main(){    scanf("%s",s);    n=strlen(s);    for(int i=0;i<26;i++)pos[n][i]=n;    f[n]=1;f[n+1]=0;//即使没有后缀仍然需要长度为1，f[n]=1；如果没有相同字符的话就f[n+1]+1，所以f[n+1]=0。     for(int i=n-1;i>=0;i--){        for(int j=0;j<26;j++)pos[i][j]=pos[i+1][j];        pos[i][s[i]-'a']=i;        f[i]=n+1;        for(int j=0;j<26;j++)f[i]=min(f[i],f[pos[i][j]+1]+1);    }    int T=f[0],p=0;    while(T--){        for(int j=0;j<26;j++)if(f[pos[p][j]+1]+1==f[p]){            putchar('a'+j);            p=pos[p][j]+1;            break;        }    }    return 0;}