Maximize the Remaining String
Contest: Codeforces Round 710 (Div. 3)
Difficulty rating: 2000
Tags: brute force, data structures, dp, greedy, strings

You are given a string $$$s$$$, consisting of lowercase Latin letters. While there is at least one character in the string $$$s$$$ that is repeated at least twice, you perform the following operation:

- you choose the index $$$i$$$ ($$$1 \le i \le |s|$$$) such that the character at position $$$i$$$ occurs at least two times in the string $$$s$$$, and delete the character at position $$$i$$$, that is, replace $$$s$$$ with $$$s_1 s_2 \ldots s_{i-1} s_{i+1} s_{i+2} \ldots s_n$$$.

For example, if $$$s=$$$"codeforces", then you can apply the following sequence of operations:

- $$$i=6 \Rightarrow s=$$$"codefrces";
- $$$i=1 \Rightarrow s=$$$"odefrces";
- $$$i=7 \Rightarrow s=$$$"odefrcs";

Given a given string $$$s$$$, find the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.

A string $$$a$$$ of length $$$n$$$ is lexicographically less than a string $$$b$$$ of length $$$m$$$, if:

- there is an index $$$i$$$ ($$$1 \le i \le \min(n, m)$$$) such that the first $$$i-1$$$ characters of the strings $$$a$$$ and $$$b$$$ are the same, and the $$$i$$$-th character of the string $$$a$$$ is less than $$$i$$$-th character of string $$$b$$$;
- or the first $$$\min(n, m)$$$ characters in the strings $$$a$$$ and $$$b$$$ are the same and $$$n < m$$$.

For example, the string $$$a=$$$"aezakmi" is lexicographically less than the string $$$b=$$$"aezus".

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

Each test case is characterized by a string $$$s$$$, consisting of lowercase Latin letters ($$$1 \le |s| \le 2 \cdot 10^5$$$).

It is guaranteed that the sum of the lengths of the strings in all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Example input:
6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz

Example output:
odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz

Editorial:
How can you check if you can perform such a sequence of operations on the string $$$s$$$ to get the string $$$t$$$? Note that each time we delete an arbitrary character that is repeated at least two times, so $$$t$$$ must be a subsequence of the string $$$s$$$ and have the same character set as the string $$$s$$$.
We will consequently build the resulting string $$$t$$$, adding characters to the end. To check if there is such a sequence of operations that turns the string $$$s$$$ into the string $$$tc?$$$ (a string that first contains the characters of the string $$$t$$$, then the character $$$c$$$, and then some unknown characters), it is enough to do the following:
• Find the minimum index $$$i$$$ such that $$$t$$$ is included in $$$s[1..i]$$$ as a subsequence;
• Find the minimum index $$$j$$$ ($$$i<j$$$) such that $$$s_j = c$$$;
• Then the substring $$$s[j+1..n]$$$ must contain all characters that are in the string $$$s$$$, but which are not in the string $$$tc$$$.
Let's denote a function that checks the criterion above as $$$can(t)$$$.
Having received the verification criterion, the following algorithm can be made:
• Initially $$$t$$$ is an empty string;
• While there is a character in the string $$$s$$$ that is not in the string $$$t$$$, we will find the maximum character $$$c$$$ not contained in $$$t$$$, but contained in $$$s$$$, for which $$$can(tc) = true$$$ and add it to the end of the string $$$t$$$.
Since at each step we take the maximum symbol for which the criterion is met, the resulting string $$$t$$$ will be the lexicographically maximum.