#P1506G. Maximize the Remaining String
Maximize the Remaining String
No submission language available for this problem.
Description
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".
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$.
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.
Input
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
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.
Samples
6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz
odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz