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:

  1. The substring tt does not occur.
  2. Every possible unique pair of symbols except for tt occurs at least once.
  3. The string begins with ( and ends with ).
  4. The string contains the same number of ( and ).
  5. 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.


1 Answer 1


There must be at least 16 since there must be at least at least $15$ pairs.

To do it with $16$, the first and last character must be the same character (why?,) which is not possible (why?)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.