Are there brackets in disguise?

Question

Someone's given us a string, but all bracket-like characters have been changed into normal ones, and we don't know which, or even how many there were. All we know is that if L1,L2,L3,...,LN were different kinds of left brackets and R1,R2,R3,...,RN were different corresponding kinds of right brackets, all being distinct (2N distinct bracket characters), a string would be valid iff it is one of (+ is normal string concatenation):

• L1+X+R1,L2+X+R2,...,LN+X+RN, where X is a valid string,

• X+Y, where X and Y are valid strings,

• Any single character that is not a bracket character.

• The empty string

We know they started out with a valid string before they changed the brackets, and they didn't change them into any characters that already existed in the string. At least one pair existed for each bracket as well. Can you reconstruct which characters were originally left and right bracket pairs (find the Li and Ri following the given conditions)?

Output the pairs of characters that were brackets. For example, if (){}[] were actually bracket characters, you might output (){}[] or {}[]() or [](){}, etc. There may be multiple ways to do this for a string, you only need to return one such that there is no bracket assignment with more pairs (see examples). Note that the output string should always have an even length.

Examples:

abcc - c cannot be a bracket, since there is no other character with two occurrences, but ab can be a bracket pair, so you would output exactly ab.

fffff - any string with at most one character cannot have brackets, so you would return the empty string or output nothing.

aedbedebdcecdec - this string cannot have any brackets because there is 1 a, 2 bs, 3 cs, 4 ds, and 5 es, so no two characters occur the same number of times, which is a requirement to have brackets.

abcd - possible assignments are ab, cd, abcd, cdab, adbc, bcad, ac, ad, bc and bd, (as well as the empty assignment, which all of them have) but you must return one of the longest assignments, so you must return abcd, cdab, adbc, or bcad.

aabbcc,abc - these both have ab, ac, and bc as valid pairs. You must return one of these pairs, doesn't matter which.

abbac - a and b have the same character count, but they can't actually work, since one of them occurs to both the left and right of all occurrences of the other. Return nothing.

aabcdb - cd and ab are the exact two bracket pairs, so output either cdab or abcd.

abcdacbd - only one pair can be achieved at once, but ab,ac,bd,cd, and ad are all of the possible pairs you can return. No matter which pair you choose, it has an instance where a single other character is within it, which prohibits any other pairs, except in the case of ad, where the other pairs bc and cb are not possible alone either, and so can't be possible with ad.

This is code golf, so shortest code in bytes wins. Input is from STDIN if possible for your language. If it isn't possible, indicate the input method in your answer.

Answer 1

Ruby, 373 bytes

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]

This uses a golfed version of the stack parser here.

It can probably be simplified further, but I don't think my brain can handle any more.

All test cases: http://ideone.com/gcqDkK

With whitespace: http://ideone.com/pLrsHg

Ungolfed (mostly): http://ideone.com/oM5gKX