Специальная задача об алгоритме сопоставления скобок
Есть строка S, состоящая из строчных букв, теперь нам нужно построить скобочную строку, которая удовлетворяет последовательности, являющейся юридически подобранной скобочной строкой. И для пары совпадающих левой и правой скобок (i, j) строка S должна удовлетворяет S[i] == S[j]. Теперь мы хотим, чтобы лексикографический порядок этой последовательности скобок был как можно меньше. Что нам делать? Можете ли вы дать некоторые идеи?
вход:
S (1 ≤ | S | ≤ 1000)
выход:
Если нет решения, выведите -1, в противном случае выведите лексикографически наименьшую допустимую строку в скобках
Случай 1:
входной образец:
aabaab
выходной образец:
() (())
случай 2:
входной образец:
ABAB
выходной образец:
-1