Problem:


Problem C: Palindrome

Problem

太郎君はそれぞれの長さがLの文字列をN個持っている。太郎君は回文が大好きなので、N個のうちいくつかの文字列を選んで好きな順番に並べることで、できるだけ長い回文を作りたい。

太郎君が作ることのできる回文の中で、最長のものを求めよ。複数ある場合は、そのうち辞書順で最小のものを出力せよ。どのように選んで並べても回文が作れない場合は、空行を出力せよ。

Input

入力は以下の形式で与えられる。

N L
s1
s2
.
.
.
sN

1行目に、文字列の数Nと文字列の長さLが与えられる。続く2行目からN &plus; 1行目に太郎君が持っている文字列s_iが与えられる。

Constraints

入力は以下の条件を満たす。

    
1 ≤ N ≤ 1000

    
1 ≤ L ≤ 30

    
s_iは英小文字からなる文字列である。

Output

最長の回文の中で辞書順最小のものを出力せよ。回文が作れない場合は空行を出力せよ。

Sample Input 1

4 2
oi
io
rr
rr

Sample Output 1

iorrrroi

Sample Input 2

5 1
a
b
c
a
c

Sample Output 2

acbca

Sample Input 3

3 3
uki
uku
uke

Sample Output 3

uku



Sample input:
4 2
oi
io
rr
rr


Sample output:
iorrrroi

Submission status: Wrong Answer

Solution code:
n, l = map(int, input().split())
ss = {}
for i in range(n):
    s = input()
    ss[s] = ss.get(s, 0) + 1
ans = ""
ma = ""
for s in sorted(ss):
    if s[::-1] == s:
        ans += s * (ss[s]//2)
        ss[s] -= 2*(ss[s]//2)
        if ss[s] > 0 and len(ma) < len(s):
            ma = s
    else:
        rev = s[::-1]
        if rev in ss:
            cnt = min(ss[s], ss[rev])
            ans += s * (ss[s]*cnt)
            ss[s] -= cnt
            ss[rev] -= cnt
print(ans + ma + ans[::-1])

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key
n, l = map(int, input().split())
ss = {}
for i in range(n):
    s = input()
    ss[s] = ss.get(s, 0) + 1
ans = ""
ma = ""
def cmp(x, y):
    l = x+y; r = y+x
    if l < r:
        return -1
    if l == r:
        return 0
    return 1
for s in sorted(ss, key=cmp_to_key(cmp)):
    if s[::-1] == s:
        ans += s * (ss[s]//2)
        ss[s] -= 2*(ss[s]//2)
        if ss[s] > 0 and len(ma) < len(s):
            ma = s
    else:
        rev = s[::-1]
        if rev in ss:
            cnt = min(ss[s], ss[rev])
            ans += s * (ss[s]*cnt)
            ss[s] -= cnt
            ss[rev] -= cnt
print(ans + ma + ans[::-1])

Submission status: Accepted

Solution code:
from functools import cmp_to_key
n, l = map(int, input().split())
ss = {}
for i in range(n):
    s = input()
    ss[s] = ss.get(s, 0) + 1
ans = ""
ma = ""
for s in sorted(ss):
    if s[::-1] == s:
        ans += s * (ss[s]//2)
        ss[s] -= 2*(ss[s]//2)
        if ss[s] > 0 and len(ma) < len(s):
            ma = s
    else:
        rev = s[::-1]
        if rev in ss:
            cnt = min(ss[s], ss[rev])
            ans += s * cnt
            ss[s] -= cnt
            ss[rev] -= cnt
print(ans + ma + ans[::-1])