Submission #1607789

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
/** whole range */
#define whole(xs) (xs).begin(), (xs).end()

namespace {
    string s;
    void input() {
        cin >> s;
    }

    const int INF = 1<<28;
    vector<int> first;
    vector<vector<int>> table;
    void construct_table(const string& s) {
        table = vector<vector<int>>(s.size(), vector<int>(26, INF));
        vector<int> last(26, INF);
        for (int i = s.size() - 1; i >= 0; i--) {
            int cur_char = s[i] - 'a';
            for (char c = 'a'; c <= 'z'; c++) {
                int next_char = c - 'a';
                table[i][next_char] = last[next_char];
            }
            last[cur_char] = i;
        }
        first = vector<int>(26, INF);
        for (int i = 0; i < s.size(); i++) {
            int cur_cindex = s[i] - 'a';
            first[cur_cindex] = min(first[cur_cindex], i);
        }
    }

    /** output whole vector. ex) vector<int>{1, 2, 3} -> '1 2 3'. */
    template<typename T>
    ostream& operator<<(ostream& os, const vector<T>& xs) {
       if (xs.empty()) return os;
       os << xs[0];
       for (auto i = 1; i < xs.size(); i++) os << ' ' << xs[i];
       return os;
    }

    void solve() {
        vector<int> found(26, false);
        int k = 1;
        int count = 0;
        for (int i = 0; i < s.size(); i++) {
            if (found[s[i] - 'a']) continue;
            found[s[i] - 'a'] = true;
            count++;
            if (count == 26) {
                k++;
                count = 0;
                fill(whole(found), false);
            }
        }

        construct_table(s);
        int n = s.size();
        vector<int> dp(n + 1, INF);
        dp[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            auto& cur = dp[i];
            for (int c = 0; c < 26; c++) {
                auto next_c = table[i][c];
                if (next_c + 1 >= n) cur = 1;
                else cur = min(cur, dp[next_c + 1] + 1);
            }
        }
        int p = -1;
        string ans = "";
        for (int i = 0; i < k; i++) {
            for (int c = 0; c < 26; c++) {
                auto next = p == -1 ? first[c] : table[p][c];
                //cout << i << " : " << c << " " << next << endl;
                if (next >= n) next = n;
                if (1 + i + dp[next] == k) {
                    p = next + 1;
                    ans.push_back(c + 'a');
                    break;
                }
            }
        }
        cout << ans << endl;
        assert(ans.size() == k);
    }
}

int main() {
    input(); solve();
    return 0;
}

Submission Info

Judge Result