进行了一些修改，现在应该变得更清晰一些。
2021/10/22 UPD:之前的打法时间复杂度假了，故进行了修正。
题意
\(~~~~\) 求字典序最小的匹配括号串使得匹配的一对括号在给定字符串 \(s\) 中对应的字符相同。或说明无解。
\(~~~~\) \(1\leq |s|\leq 10^5.\)
题解
\(~~~~\) 先来判有没有解，可以直接把字符串当成括号串来放进栈里面匹配，栈顶与当前字符相同说明这样可以放匹配括号，则弹出，否则入栈。最后只要栈为空就是有解的。
\(~~~~\) 首先考虑怎么求某一个区间是否合法（但在正常的做题思路中它应该在后面），显然如果在栈没有扫到这个区间与刚好扫过这个区间之后栈内的字符是相同的则该区间合法。记 \(hash_i\) 表示在 \(i\) 字符执行完进栈/弹栈操作后的栈内的 \(hash\) 值，那么当 \(hash_{l-1}=hash_r\) 时，区间 \([l,r]\) 是合法的。
\(~~~~\) 那么怎么来求解某个合法区间呢？我们记 \(solve(l,r)\) 为求解一个已知区间 \([l,r]\) 的答案的过程，我们现在可以知道：
- \(l\) 处应放置左括号 ：显然，因为区间合法，第一个字符只有放左括号才可能匹配上后面的字符。
- 与 \(l\) 处匹配的右括号应该放在可能的最远的位置，设为 \(pos\)，那么\([pos+1,r]\) 会被划分为一个区间，则 \(pos\) 应该满足 \(hash_{pos}=hash_r\) 且 \(s_l=s_{pos}\)。
- 同时为了满足字典序更小，右括号应该被放在尽可能远的位置，所以 \(pos\) 应取可行的最大值。
\(~~~~\) 关于怎么快速找到 \(pos\) 可行的最大值？用 map 维护最大的位置 \(j\) ，满足 \(s_j\) 为给定字符与给定hash值，同时顺便维护某个位置上一个条件与它相同的位置，最后暴力跳即可。
\(~~~~\) 这样，区间就被我们分成了三个部分：\(l\) ，\(pos\) 、\([l+1,pos-1]\) 和 \([pos+1,r]\) 。由于 \(hash_{pos}=hash_{r}\) ，所以区间 \([pos+1,r]\) 是合法的。而区间 \([l,pos]\) 也一定是合法的，在合法区间两边同时去掉一位，若这两位对应的字符相同，余下的区间也一定合法。（这两个字符在栈里面会最后消掉，故扫描到最后一位之前一定与第一位刚进栈时栈内字符串相等）所以 \([l+1,pos-1]\) 也一定合法。
\(~~~~\) 那既然这两个区间是合法的，我们可以继续执行 \(solve\) 过程就可以求解这两个区间。
2021/10/22 UPD
\(~~~~\) 但是，求出全局最靠右的满足该条件的位置再暴力跳回来的复杂度是假的 \(n \log n\)，因为当所有字符相同时，正如上面一篇题解所述复杂度应为 \(0+1+\dots+(\frac{n}{4}-1)=\frac{n^2}{16}\)，所以这个办法其实会被卡。
\(~~~~\) 解决方法是：每次先遍历右区间 \([pos+1,r]\)，同时更新 map 存储的某一条件的位置到尽可能靠左的地方，这样由于从右往左处理区间，所以每次 map 找到的位置都是在当前区间右边但尽可能靠近它的位置，这样暴力跳的次数就不会太多。当然你也可以把 \(hash\) 值离散化后用 vector 存下来，每次二分合适的位置，只是会带大常数。
\(~~~~\) 时间复杂度 \(\mathcal{O(n\log n)}\).
代码
#include <map>
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mp(a,b) make_pair(a,b)
#define ll long long
#define ull unsigned long long
using namespace std;
const ull base=131;
char Ans[100005],str[100005],sta[100005];
int lef[100005],lst[100005];
ull P[100005],Hash[100005];
int Top;
map<pair<ll,int>,int>M;
void solve(int l,int r)
{
if(r<=l) return;
int pos=M[mp(Hash[r],str[l]-'a')];
while(pos>r) pos=lef[pos];
Ans[l]='(';Ans[pos]=')';
M[mp(Hash[pos],str[pos]-'a')]=pos;
solve(pos+1,r);solve(l+1,pos-1);
}
int main() {
scanf("%s",str+1);
int len=strlen(str+1);
P[0]=1;
for(int i=1;i<=len;i++) P[i]=P[i-1]*base;
ull now=0;
for(int i=1;i<=len;i++)
{
if(str[i]==sta[Top]) now-=P[Top--]*(str[i]-'a'+1);
else now+=P[++Top]*(str[i]-'a'+1),sta[Top]=str[i];
Hash[i]=now;
}
if(Top) return puts("-1")&0;
for(int i=1;i<=len;i++)
{
lef[i]=M[mp(Hash[i],str[i]-'a')];
M[mp(Hash[i],str[i]-'a')]=i;
}
solve(1,len);
puts(Ans+1);
return 0;
}