Given a string of characters (say a, b, ...) I want to wrap those characters by tags <a>...</a>, <b>...</b>, and so on, so that for each character the innermost tag wrapping the character should match with it.

For instance, considering a string aabbaaca, we may have

  • <a>aa</a><b>bb</b><a>aa</a><c>c</c><a>a</a> (naive way)
  • <a>aa<b>bb</b>aa<c>c</c>a</a> (optimal way)
  • <a>aa<b>bb<a>aa<c>c</c></a></b>a</a>

to write a few. I want to minimize the number of such tags. Is there a known problem to which my problem can be reduced?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.