308363: CF1506G. Maximize the Remaining String

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Maximize the Remaining String

题意翻译

给你一个由小写英文字母组成的字符串 $s$,你需要去掉一部分字符,使得操作后得到的字符串 $t$ 满足在 $s$ 中出现的字母每种只保留一个并且最大化 $t$ 的字典序。 ### 输入格式 多测 第一行一个正整数 $T$($1\le T\le 10^4$)表示数据组数。 接下来 $T$ 行,每行一个由小写字母组成的字符串 $s$($\sum|s|\le 2\times 10^5$)。 ### 输出格式 输出 $T$ 行 对于每组输入的 $s$,输出一行一个字符串表示满足要求且字典序最大的 $t$。

题目描述

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.

输入输出样例

输入样例 #1

6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz

输出样例 #1

odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz

Input

题意翻译

给你一个由小写英文字母组成的字符串 $s$,你需要去掉一部分字符,使得操作后得到的字符串 $t$ 满足在 $s$ 中出现的字母每种只保留一个并且最大化 $t$ 的字典序。 ### 输入格式 多测 第一行一个正整数 $T$($1\le T\le 10^4$)表示数据组数。 接下来 $T$ 行,每行一个由小写字母组成的字符串 $s$($\sum|s|\le 2\times 10^5$)。 ### 输出格式 输出 $T$ 行 对于每组输入的 $s$,输出一行一个字符串表示满足要求且字典序最大的 $t$。

加入题单

上一题 下一题 算法标签: