Решение задачи Две скобочные последовательности с Codeforces

Вам задано две скобочные последовательности (не обязательно правильные) s и t, состоящие только из символов '(' и ')'. Вы хотите построить кратчайшую правильную скобочную последовательность, которая содержит обе заданные скобочные последовательности в качестве подпоследовательностей (не обязательно подряд идущих).

Напомним, что такое правильная скобочная последовательность:

() является правильной скобочной последовательностью;
если S является правильной скобочной последовательностью, то (S) является правильной скобочной последовательностью;
если S и T являются правильными скобочными последовательностями, то ST (конкатенация S и T) тоже является правильной скобочной последовательностью.
Напомним, что подпоследовательностью строки s называется такая строка t, которая получается из s при помощи удаления некоторого (возможно, нулевого) количества символов. Например, «coder», «force», «cf» и «cores» являются подпоследовательностями «codeforces», а «fed» и «z» — нет.