Submission #1606244

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
string A;
int S[200001][26];
int dp[200001];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> A;
  N = A.length();

  rep(i, 26) S[N][i] = N;
  for (int i=N-1; i>=0; i--) {
    rep(j, 26) S[i][j] = S[i+1][j];
    S[i][A[i]-'a'] = i;
  }

  rep(i, N+1) dp[i] = INF;
  dp[N] = 0;
  for (int i=N-1; i>=0; i--) {
    rep(j, 26) {
      //if (A[i]-'a' == j) continue;
      dp[i] = min(dp[i], dp[S[i+1][j]]+1);
    }
  }

  int L = INF;
  rep(i, 26) L = min(L, 1 + dp[S[0][i]]);
  //rep(i, N)cout<<dp[i]<<",";cout<<"\n";
  string o = "";
  int pos = 0;
  rep(i, L) {
    int t = -1;
    assert(pos <= N);
    rep(j, 26) {
      //assert(S[pos][j] <= N);
      int to = S[pos][j];
      if (dp[min(to+1, N)] <= L-1-i) {
        pos = to+1;
        //cout<<"pos="<<pos<<"\n";
        t = j;
        break;
      }
    }
    assert(t != -1);
    o += (char)('a'+t);
  }
  assert(o.size() == L);
  cout << o << "\n";
  return 0;
}

Submission Info

Judge Result