1744. 最长括号匹配子串

【题目描述】

已知一括号字符串，其中只包含左右圆括号"(" 和 ")"，请编程计算其最长的符合括号匹配规则的子串。

【输入格式】

一行，包含一个括号字符串；

【输出格式】

如果输入的字符串没有匹配的子串，输出-1；

否则，输出2行；

第一行一个整数，表示输入的字符串最长的符合括号匹配子串的长度；

第二行，一个字符串，表示符合题意的括号子串，如果存在多个，请输出最右侧的子串；

【样例输入1】

(()())(((((()))((( 

【样例输出1】

6
((()))

【样例1说明】

如样例所示，2个红色匹配子串长度均为6，根据题意要求，存在多个最优解时，输出最右侧的解，故第二行输出((()));

【样例输入2】

)))(((

【样例输出2】

-1

【数据规模与约定】

$40$%的数据，$length(字符串)<=1,200$;

$80$%的数据，$length(字符串)<=1×10^5$;

$100$%的数据，$length(字符串)<=1×10^6$;

【来源】

MR cheng