部分列DP(WIP)
(string/subseceqence.cpp)

#pragma once
#include<string>
#include<vector>
#include<set>
#include<tuple>

/**
 * @brief 部分列DP(WIP)
 */

struct subsequence{
    struct node;
    using np=node*;
    struct node{
        np ch[26]={};
        int idx;
        char c;
        node(int idx,char c):idx(idx),c(c){}
    };
    std::string s;int n;
    std::vector<std::vector<int>>m;
    std::vector<np>v;
    np root=0;
    subsequence(std::string s):s(s),n(s.size()),m(n+1,std::vector<int>(26,-1)),v(n+1){
        for(int i=n-1;i>=0;--i){
            m[i]=m[i+1];
            m[i][s[i]-'a']=i;
        }
        for(int i=0;i<n+1;++i)v[i]=new node(i,(i?s[i-1]:'#'));
        for(int i=0;i<n;++i){
            for(int j=0;j<26;++j){
                if(~m[i][j])v[i]->ch[j]=v[m[i][j]+1];
            }
        }
        root=v[0];
    }
    //ここから問題ごとに書く
    std::vector<long long>dp;
    void dp2(){
        dp.resize(n+1);
        for(int i=n;i>=0;--i){
            np t=v[i];
            dp[i]=;
            for(int j=0;j<26;++j){
                if(!t->ch[j])dp[i]=1;
                else dp[i]=min(dp[i],dp[t->ch[j]->idx]+1);
            }
        }
    }
    string ans;
    void dfs(np t){
        for(int i=0;i<26;i++){
            if(!t->ch[i]){
                if(t!=root)ans+=t->c;
                ans+=char(i+'a');
                return;
            }
            if(dp[t->ch[i]->idx]==dp[t->idx]-1){
                if(t!=root)ans+=t->c;
                dfs(t->ch[i]);
                return;
            }
        }
    }
    string solve(){
        dp2();
        dfs(root);
        return ans;
    }
};

#line 2 "string/subseceqence.cpp"
#include<string>
#include<vector>
#include<set>
#include<tuple>

/**
 * @brief 部分列DP(WIP)
 */

struct subsequence{
    struct node;
    using np=node*;
    struct node{
        np ch[26]={};
        int idx;
        char c;
        node(int idx,char c):idx(idx),c(c){}
    };
    std::string s;int n;
    std::vector<std::vector<int>>m;
    std::vector<np>v;
    np root=0;
    subsequence(std::string s):s(s),n(s.size()),m(n+1,std::vector<int>(26,-1)),v(n+1){
        for(int i=n-1;i>=0;--i){
            m[i]=m[i+1];
            m[i][s[i]-'a']=i;
        }
        for(int i=0;i<n+1;++i)v[i]=new node(i,(i?s[i-1]:'#'));
        for(int i=0;i<n;++i){
            for(int j=0;j<26;++j){
                if(~m[i][j])v[i]->ch[j]=v[m[i][j]+1];
            }
        }
        root=v[0];
    }
    //ここから問題ごとに書く
    std::vector<long long>dp;
    void dp2(){
        dp.resize(n+1);
        for(int i=n;i>=0;--i){
            np t=v[i];
            dp[i]=;
            for(int j=0;j<26;++j){
                if(!t->ch[j])dp[i]=1;
                else dp[i]=min(dp[i],dp[t->ch[j]->idx]+1);
            }
        }
    }
    string ans;
    void dfs(np t){
        for(int i=0;i<26;i++){
            if(!t->ch[i]){
                if(t!=root)ans+=t->c;
                ans+=char(i+'a');
                return;
            }
            if(dp[t->ch[i]->idx]==dp[t->idx]-1){
                if(t!=root)ans+=t->c;
                dfs(t->ch[i]);
                return;
            }
        }
    }
    string solve(){
        dp2();
        dfs(root);
        return ans;
    }
};