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
, whereX
is a valid string,X+Y
, whereX
andY
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.
abcd
, the outputadbc
would also be acceptable, right? \$\endgroup\$