题解

思路

把 ( 看成 $1$，) 看成 $-1$，合法括号序列等价于总和为 $0$ 且所有前缀和非负。

做法

交换不改变两种括号的数量，因此先用替换使它们各有 $N$ 个：左括号过多时从右往左改，右括号过多时从左往右改，这会在相同替换次数下尽量抬高前缀和。设调整后的最小前缀和为 $m$，交换最左边导致负前缀的 ) 与右侧的 ( 每次能将需要修复的最小值提高 $2$，所以还需要 $\lceil -m/2\rceil$ 次此类修复。

一次交换也可以用两次替换实现，因而其有效代价为 $\min(A,2B)$。

复杂度

扫描字符串完成数量调整和最小前缀和统计即可，时间复杂度为 $O(N)$，额外空间复杂度为 $O(1)$。