I've got an alphabet consisting of four symbols: (
, )
, e
, and t
. The inspiration for them are the four basic types of XML elements: a start tag (like <foo>), an end tag (like </foo>), an empty tag (like <foo/>), and non-markup text (like FOO).
We call a string made up of these symbols valid if it meets the following conditions:
- The substring
tt
does not occur. - Every possible unique pair of symbols except for
tt
occurs at least once. - The string begins with
(
and ends with)
. - The string contains the same number of
(
and)
. - The cumulative count of
(
is everywhere greater than the cumulative count of)
, except at the beginning and the end.
The question is: What is the length of the shortest valid string?
An extensive brute-force search has yielded valid strings of length 17 (the string (t((e())eet)()te)
is one example) but none of length 16. Rules 1 and 2 mean that there cannot be any valid strings with fewer than 16 symbols. So the question can be rephrased as: Do any valid strings of length 16 exist? If yes, can you give an example? If no, can you prove it?
If rule 3 is omitted, then strings of length 16 are possible, for example e()t(te)((et))ee
.