시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 62 | 30 | 26 | 65.000% |
We define a valid bracket sequence as a string that is either:
Let B be a valid bracket sequence of length N. We define Bi to be the i-th character of sequence B. For two indices i and j, 1 ≤ i < j ≤ N, we say that Bi and Bj are matching brackets if:
Let S be a string of lowercase English letters. We define Si to be the i-th character of string S. We say that a valid bracket sequence B matches S if:
For a given string S consisting of N lowercase letters, find the lexicographically smallest valid bracket sequence that matches S, or print -1 if no such bracket sequence exists.
The input contains a string S of N lowercase letters on the first line.
In the output you should write either a string B with N characters that represents the lexicographically smallest bracket sequence that matches the input string, or -1 if no such bracket sequence exists.
abbaaa
(()())
abab
-1
Another valid bracket sequence is (())(), but this is not the smallest lexicographic solution.
There is no valid bracket sequence that matches the given string.