E - Rvom and Rsrev
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
a と b からなる文字列 S が与えられます。S に以下の操作を 0 回以上繰り返してできる辞書順最大の文字列を求めてください。
- 同一の文字である S の 2 箇所の文字を選ぶ。それらの間の文字列を前後反転させ、選んだ 2 文字を削除する。すなわち、S の i 文字目を s_i と表すことにすれば、s_i=s_j なる i < j を選んで S を s_1\dots s_{i-1}s_{j-1}\dots s_{i+1}s_{j+1}\dots s_{|S|} で置き換える。
なお、この問題ではテストケースが T 個与えられます。i 個目のテストケースは文字列 S_i で表され、S=S_i に対して上記の問題を解く問題です。
制約
- 1 \leq T \leq 2\times 10^5
- 1 \leq |S_i|\quad (i=1,\dots, T)
- 1 \leq |S_1| + \dots + |S_T| \leq 2\times 10^5
- S_i は
aとbからなる
入力
入力は以下の形式で標準入力から与えられる。
T S_1 \vdots S_T
出力
T 行出力せよ。i 行目には、S_i に操作を 0 回以上繰り返してできる辞書順最大の文字列を出力せよ。
入力例 1
20 abbaa babbb aabbabaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbabaaaaabbaababaaabbabbbbbaaaaa babbbaaaabaababbbabaabaaaaababaa bbaababababbbaaabaabababaabbabab abaabbabaabaaaaabaaaabbaabaaaaab aabababbabbabbabbaaaabbabbbabaab aabababbabbbbaaaabbaaaaabbaaaabb abbbbaabaaabababaaaababababbaabb aaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb abababaaababaaabbbbbaaaaaaabbbbb aabbaaaaababaabbbbbbbbbaabaaabbb babababbababbbababbbbbababbbabbb bbbbababbababbbabababbabbabbbbbb aaaaaaaaaaaaaaaaababababbbabbbbb aabababbabbabababababababbbbabbb
出力例 1
bba bba bbba aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbaaaaaaaa bbbbbbbbbbbbbaaaaaaa bbbbbbbbbbbbbbbb bbbbbbbbbb bbbbbbbbbbbbbbbbab bbbbbbbbbbbbbb bbbbbbbbbbbbbabb abbbbbbbbb bbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbaaaaaaaaa bbbbbbbbbbbbbbbaaaaa bbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbba bbbbbbbbbaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbba
- 1 個目のテストケースは、1 文字目と 4 文字目に対して操作を行うことで S を
bbaにできます。 - 2 個目のテストケースは、1 文字目と 5 文字目に対して操作を行うことで S を
bbaにできます。 - 3 個目のテストケースは、1 文字目と 2 文字目に対して操作を行うことで S を
bbabaaにでき、その後 3 文字目と 5 文字目に対して操作を行うことで S をbbbaにできます。
Score : 800 points
Problem Statement
Given is a string S consisting of a and b. Find the lexicographically greatest string that can be obtained by applying the following operation to S zero or more times:
- Choose two characters of S that are the same letter. Reverse the string between them and delete the chosen two characters. In other words: let s_i denote the i-th character of S. Choose i < j such that s_i = s_j and replace S with s_1\dots s_{i-1}s_{j-1}\dots s_{i+1}s_{j+1}\dots s_{|S|}.
In this problem, you are given T test cases. The i-th test case is represented as S_i and asks you to solve the problem above for S = S_i.
Constraints
- 1 \leq T \leq 2\times 10^5
- 1 \leq |S_i|\quad (i=1,\dots, T)
- 1 \leq |S_1| + \dots + |S_T| \leq 2\times 10^5
- S_i consists of
aandb.
Input
Input is given from Standard Input in the following format:
T S_1 \vdots S_T
Output
Print T lines. The i-th line should contain the lexicographically greatest string that can be obtained by applying the operation to S_i zero or more times.
Sample Input 1
20 abbaa babbb aabbabaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbabaaaaabbaababaaabbabbbbbaaaaa babbbaaaabaababbbabaabaaaaababaa bbaababababbbaaabaabababaabbabab abaabbabaabaaaaabaaaabbaabaaaaab aabababbabbabbabbaaaabbabbbabaab aabababbabbbbaaaabbaaaaabbaaaabb abbbbaabaaabababaaaababababbaabb aaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb abababaaababaaabbbbbaaaaaaabbbbb aabbaaaaababaabbbbbbbbbaabaaabbb babababbababbbababbbbbababbbabbb bbbbababbababbbabababbabbabbbbbb aaaaaaaaaaaaaaaaababababbbabbbbb aabababbabbabababababababbbbabbb
Sample Output 1
bba bba bbba aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbaaaaaaaa bbbbbbbbbbbbbaaaaaaa bbbbbbbbbbbbbbbb bbbbbbbbbb bbbbbbbbbbbbbbbbab bbbbbbbbbbbbbb bbbbbbbbbbbbbabb abbbbbbbbb bbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbaaaaaaaaa bbbbbbbbbbbbbbbaaaaa bbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbba bbbbbbbbbaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbba
- In the 1-st test case, we can do the operation for the 1-st and 4-th characters to make S
bba. - In the 2-nd test case, we can do the operation for the 1-st and 5-th characters to make S
bba. - In the 3-rd test case, we can do the operation for the 1-st and 2-nd characters to make S
bbabaa, then do it for the 3-rd and 5-th characters to make Sbbba.