Apakah ada tanda kurung yang menyamar?

Seseorang memberi kami string, tetapi semua karakter seperti braket telah diubah menjadi yang normal, dan kami tidak tahu yang mana, atau bahkan berapa banyak. Yang kita tahu adalah bahwa jika L1,L2,L3,...,LNada berbagai jenis kurung kiri dan R1,R2,R3,...,RNberbagai jenis kurung kanan yang berbeda, semuanya berbeda (2N karakter kurung berbeda), sebuah string akan valid jika itu salah satu (+ adalah penggabungan string normal):

• L1+X+R1,, L2+X+R2... LN+X+RN,, di mana Xstring yang valid,

• X+Y, di mana Xdan Yadalah string yang valid,

• Setiap karakter tunggal yang bukan karakter braket.

• String kosong

Kami tahu mereka mulai dengan string yang valid sebelum mereka mengubah tanda kurung, dan mereka tidak mengubahnya menjadi karakter apa pun yang sudah ada di string. Setidaknya ada satu pasangan untuk masing-masing braket. Bisakah Anda merekonstruksi karakter mana yang awalnya kiri dan kanan pasang braket (temukan Lidan Riikuti syarat yang diberikan)?

Keluarkan pasangan karakter yang merupakan tanda kurung. Misalnya, jika (){}[]benar-benar braket karakter, Anda mungkin keluaran (){}[]atau {}[]()atau [](){}, dll Mungkin ada beberapa cara untuk melakukan ini untuk string, Anda hanya perlu untuk kembali satu sehingga tidak ada braket tugas dengan lebih pasang (lihat contoh). Perhatikan bahwa string keluaran harus selalu memiliki panjang genap.

Contoh:

abcc- ctidak bisa menjadi braket, karena tidak ada karakter lain dengan dua kejadian, tetapi abbisa menjadi pasangan braket, sehingga Anda akan menampilkan dengan tepat ab.

fffff - string apa pun dengan paling banyak satu karakter tidak dapat memiliki tanda kurung, jadi Anda akan mengembalikan string kosong atau tidak menghasilkan apa-apa.

aedbedebdcecdec - string ini tidak dapat memiliki tanda kurung karena ada 1 a, 2 bs, 3 cs, 4 ds, dan 5 es, jadi tidak ada dua karakter yang muncul dalam jumlah yang sama, yang merupakan persyaratan untuk memiliki tanda kurung.

abcd- mungkin tugas yang ab, cd, abcd, cdab, adbc, bcad, ac, ad, bcdan bd, (serta tugas kosong, yang semua dari mereka memiliki), tetapi Anda harus kembali salah satu tugas terpanjang, sehingga Anda harus kembali abcd, cdab, adbc, atau bcad.

aabbcc, abc- tersebut keduanya memiliki ab, ac, dan bcsebagai pasangan yang sah. Anda harus mengembalikan salah satu dari pasangan ini, tidak masalah yang mana.

abbac- a dan b memiliki jumlah karakter yang sama, tetapi mereka tidak dapat benar-benar bekerja, karena salah satunya terjadi di kiri dan kanan semua kejadian yang lain. Kembalikan apa-apa.

aabcdb- cddan abmerupakan dua pasangan braket yang tepat, sehingga menghasilkan salah satu cdabatau abcd.

abcdacbd- hanya satu pasangan dapat dicapai sekaligus, tapi ab, ac, bd, cd, dan adsemua dari pasangan yang mungkin Anda dapat kembali. Tidak peduli pasangan mana yang Anda pilih, itu memiliki contoh di mana satu karakter lain di dalamnya, yang melarang pasangan lain, kecuali dalam kasus ad, di mana pasangan lain bcdan cbtidak mungkin sendiri, jadi tidak mungkin dengan ad.

Ini adalah kode golf, jadi kode terpendek dalam byte menang. Masukan dari STDIN jika memungkinkan untuk bahasa Anda. Jika tidak memungkinkan, tunjukkan metode input dalam jawaban Anda.

Ruby, 373 byte

i=gets.chomp
b=[*(i.chars.group_by{|x|x}.group_by{|x,y|y.size}.map{|x|s=x[1].size
x[1][0...s-s%2].map{|x|x[0]}*''}*'').chars.each_slice(2)]
puts [*[*b.size.downto(1).map{|n|b.combination(n).map{|t|[t*'',(h=Hash[t]
s=[]
o=1
i.each_char{|c|s.push(c)if h.keys.include?c
(o=false if s.empty?||!h[s.pop].eql?(c))if h.values.include?c}
o ?s.empty?: o)]}}.find{|x|x[0][1]}][0]][0]

Ini menggunakan versi parser stack yang di-golf di sini .

Ini mungkin dapat disederhanakan lebih lanjut, tetapi saya tidak berpikir otak saya dapat menangani lagi.

Semua kasus uji: http://ideone.com/gcqDkK

Dengan spasi putih: http://ideone.com/pLrsHg

Tidak berkelompok (kebanyakan): http://ideone.com/oM5gKX