C++ Library for Competitive Programming
/*
* @title 文字列/部分列 DP
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/arc081/tasks/arc081_c
*/
#include <iostream>
#include <string>
#include <vector>
#include "emthrm/string/subsequence_dp.hpp"
int main() {
constexpr int SIGMA = 26;
std::string a;
std::cin >> a;
const int n = a.length();
const std::vector<std::vector<int>> nxt =
emthrm::subsequence_dp(a, 'a', SIGMA);
std::vector<int> dp(n + 1, n + 1), next_char(n, -1);
dp[n] = 1;
for (int i = n - 1; i >= 0; --i) {
for (int c = 0; c < SIGMA; ++c) {
const int len = (nxt[i][c] == n ? 0 : dp[nxt[i][c] + 1]) + 1;
if (len < dp[i]) {
dp[i] = len;
next_char[i] = c;
}
}
}
std::string ans = "";
for (int i = 0; i < n;) {
ans += 'a' + next_char[i];
i = nxt[i][next_char[i]] + 1;
}
std::cout << ans << '\n';
return 0;
}
#line 1 "test/string/subsequence_dp.test.cpp"
/*
* @title 文字列/部分列 DP
*
* verification-helper: IGNORE
* verification-helper: PROBLEM https://atcoder.jp/contests/arc081/tasks/arc081_c
*/
#include <iostream>
#include <string>
#include <vector>
#line 1 "include/emthrm/string/subsequence_dp.hpp"
#include <algorithm>
#line 7 "include/emthrm/string/subsequence_dp.hpp"
namespace emthrm {
std::vector<std::vector<int>> subsequence_dp(
const std::string& s, const char basis = 'a', const int sigma = 26) {
const int n = s.length();
std::vector<std::vector<int>> nx(n, std::vector<int>(sigma, n));
nx[n - 1][s[n - 1] - basis] = n - 1;
for (int i = n - 2; i >= 0; --i) {
std::copy(nx[i + 1].begin(), nx[i + 1].end(), nx[i].begin());
nx[i][s[i] - basis] = i;
}
return nx;
}
} // namespace emthrm
#line 13 "test/string/subsequence_dp.test.cpp"
int main() {
constexpr int SIGMA = 26;
std::string a;
std::cin >> a;
const int n = a.length();
const std::vector<std::vector<int>> nxt =
emthrm::subsequence_dp(a, 'a', SIGMA);
std::vector<int> dp(n + 1, n + 1), next_char(n, -1);
dp[n] = 1;
for (int i = n - 1; i >= 0; --i) {
for (int c = 0; c < SIGMA; ++c) {
const int len = (nxt[i][c] == n ? 0 : dp[nxt[i][c] + 1]) + 1;
if (len < dp[i]) {
dp[i] = len;
next_char[i] = c;
}
}
}
std::string ans = "";
for (int i = 0; i < n;) {
ans += 'a' + next_char[i];
i = nxt[i][next_char[i]] + 1;
}
std::cout << ans << '\n';
return 0;
}