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