算法

(贪心) $O(t * s.size())$

本题实际上就是让我们求 $s$ 字典序最大的子序列，该子序列包含 $s$ 的所有不同字符，且只包含一次。
可以考虑贪心，从前往后扫描每个字符，在扫描的时候用另外一个字符串 $T$ 去记录下当前的答案是多少，每次去判断一下 $T$ 的最后一个字母 $T_j$，如果 $T_j < S_i$ 且 $T_j$ 这个字母可以被删掉（也就是后面还出现过）则删掉 $T_j$。

不难看出不删 $T_j$ 的方案的字典序显然不如删掉 $T_j$ 的的方案的字典序大，所以最优解一定是删掉 $T_j$ 的方案。

同时这题lc上有原题：去除重复字母

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::string;
using std::map;

int main() {
    int t;
    cin >> t;

    while (t--) {
        string s, stk;
        cin >> s;
        map<char, bool> ins;
        map<char, int> last;
        for (int i = 0; i < s.size(); ++i) last[s[i]] = i;

        rep(i, s.size()) {
            if (ins[s[i]]) continue;
            while (stk.size() and stk.back() < s[i] and last[stk.back()] > i) {
                ins[stk.back()] = false;
                stk.pop_back();
            }
            stk += s[i];
            ins[s[i]] = true;
        }

        cout << stk << '\n';
    }

    return 0;
}