A strongest string

2.9

15 votes
Algorithms, String Manipulation, String manipulation
Problem

You are given a string S that consists of N lowercase letters of the Latin alphabet.
In one step, you can remove any letter in the string. You are required to determine the maximum lexicographic sentence of words you can leave so that all letters are different.

The lexicographical order on the set of all these finite words orders the words in the following manner:

  1. You are given two different words of the same length, for example, a=a1, a2, ...,ak and b=b1, b2, ..., bk. The order of these two words depends on the alphabetic order of the symbols on the first place i where the two words are different (counting from the beginning of the words), a<b if and only if ai<bi in the underlying order of alphabet A.
  2. If two words have different lengths, then the usual lexicographical order pads the shorter one with 'blanks' (a special symbol that is treated as smaller than every element of A) until the words are made of the same length. Now, the words are compared as in the previous case.

Input format

  • The first line contains T denoting the number of test cases.
  • The first line of each test case contains N denoting the length of string S.
  • The second line of each test case contains string S.

Output format

For each test case, print the answer.

Constraints
1T101N105|S|=N

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For the first string, the answer is "yc" because "yc" > "ybd", "yc" > "y", "yc" > "yd", "y" > "a", "y" > "b" and "y" > "c".

For the second string, the answer is "z" because strings "zz" and "zzz" have the same letters.

Editor Image

?