Magic Strings

Problem code: J5

All Submissions

All submissions for this problem are available.

Magic strings, invented by the Bytelandians, are strings that contain immense magical power within themselves. Magic strings could bring luck and happiness to the Bytelandian citizens. Formally, a string S of length n is a magic string if it satisfies the following conditions:

All letters of S are lowercase letters of the English alphabet.
S_i is lexicographically smaller than S_n-i+1 for all odd i from 1 to [n/2].
S_i is lexicographically greater than S_n-i+1 for all even i from 1 to [n/2].

(S_i (1 ≤ i ≤ n) denotes the i^th character of S). For example, the word "difference" is a magic string, while "similar" is not.

Given a string S of lowercase English letters, write a program to find the longest magic string than can be obtained by removing some letters of S. If there are more than one solutions, choose the longest magic string which is lexicographically smallest.

Input

The first line contains t, the number of test cases (about 10). Then t test cases follow. Each test case contains a string S written in a single line. S does not contain more than 2000 letters.

Output

For each test case, print the longest magic string that is lexicographically smallest in a single line.

Example

Input
3
difference
similarq
caaat

Output
difference
imilaq
aat

Date:	2009-10-15
Time limit:	2s
Source limit:	50000
Languages:	C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK CAML CLPS PRLG WSPC BF ICK TEXT JS

Submit

Comments

Login or Register to post a comment.

Can any 1 eloborate w.r.t

santhosh somashekaraiah - 2nd Nov,2009 12:03:28.

Can any 1 eloborate w.r.t "similarq"?

How we get "imilaq"? I thought it to be "imilarq" ?

The sample output is correct.

Stephen Merriman - 2nd Nov,2009 13:58:12.

The sample output is correct.

Re-read the problem

Admin - 2nd Nov,2009 14:01:12.

Re-read the problem statement. 'imilarq' is not a magic string.

admin, please delete the

Stephen Merriman - 3rd Nov,2009 09:26:02.

admin, please delete the previous two comments ASAP :(

plz xplain the xample:-- for

gurpreet - 3rd Nov,2009 14:22:02.

plz xplain the xample:-- for difference isn't it that ceeffiendr the corrsct answer because cd,ee,fa alsso of length 5 and lexicographically smaller than caaat also if we cionsider for 3 letters word isn't it that aac is correct answer because aat>aac lexicographically plz correct me if i m wrng thnx in advance

plz xplain the xample:-- for

gurpreet - 3rd Nov,2009 14:29:11.

sry my mistake must have read

gurpreet - 3rd Nov,2009 15:02:40.

sry my mistake

must have read the question carefullyy

i hv understood the question now......

I have a few doubts, would

Prashanth K S - 4th Nov,2009 22:09:39.

I have a few doubts, would appreciate it a lot of someone can clarify these.

1) According to the magic string condition, lesser than and greater than conditions are specified. What about equal to condition? Maybe my next question would answer this.

2) Are the inputs provided all already magic strings? As in, in the test cases on the server.

3) In the first test case in the example, there is no change in the output as compared to the input string. Why is this so? Shouldn't I mandatorily remove some characters to form a new magic string? I am unable to understand what happened here.

4) I am unable to understand the meaning of "longest string that is lexicographically smallest".

I am sorry if I throwing some clues in with these questions. Please ignore in such a case.

@Prashanth I guess equal is

Shilp Gupta - 5th Nov,2009 01:09:11.

@Prashanth I guess equal is not to be considered either smaller or greater because of sample test 3. Otherwise answer would have been "aaat" or at least "aaa"

My interpretation of "longest string that is lexicographically smallest" rests on a case like "similarq". obviously "imilar" and "imilaq" both are longest magic strings, but "imilaq" is smaller lexicographically - so, consider the set of solutions with longest magic strings and choose the lexicographically smallest among them

unfortunately, the solution is not so obvious to me (yet?)

are the judge's pc is pentium

Shiplu - 5th Nov,2009 22:43:36.

are the judge's pc is pentium 1 or even more backdated, my codes time complexity is about

8 * 10 ^7 in total(including 10 test cases). I am getting TLE, this is redicolous.

10^9 runs in 1 sec in a normal pc like celeron D.

The machine configurations

Admin - 6th Nov,2009 13:52:12.

The machine configurations can be found on the wiki at www.codechef.com/wiki .

I think you shouldn't blame

Ngô Minh Đức - 7th Nov,2009 08:03:57.

I think you shouldn't blame the speed of the server. The fact that there are many people solved this problem on this server means that your algorithm may be just not fast enough.