题目描述

难度分:$1400$

输入$n(1 \leq n \leq 10^5)$和$n$个括号字符串，字符串长度之和$\leq 5 \times 10^5$。

你需要从中选出$2m$个括号串，两两一对，拼接成$m$个合法括号字符串。

输出$m$的最大值。

输入样例$1$

3
)
()
(

输出样例$1$

2

输入样例$2$

2
()
()

输出样例$2$

4

算法

贪心

每个字符串从左往右遍历，按照括号匹配的思路计算最后剩下的左括号“净含量”$left$和右括号“净含量”$right$。观察之后可以发现如下规律：

1. 如果$left \gt 0$和$right \gt 0$同时成立，这个字符串就应该被抛弃掉，不可能存在能和它匹配出合法括号串的另一个字符串。
2. 如果$left \gt 0$，就把它记录到哈希表$lcnt$中（$lcnt$的映射关系为“左括号净含量 $\rightarrow$ 这个净含量的字符串数目”）。
3. 如果$right \gt 0$，就把它记录到哈希表$rcnt$中（$rcnt$的映射关系为“右括号净含量 $\rightarrow$ 这个净含量的字符串数目”）。
4. 如果$left=right=0$，记录满足这个的字符串数目$zcnt$，这样的字符串可以两两配对，一共产生$[\frac{zcnt}{2}]$个合法括号串（其中$[.]$表示对$.$的向下取整操作）。

接下来就是让左括号“净含量”与右括号“净含量”相等的串进行配对，对于一个在$lcnt$和$rcnt$都存在的“净含量”$x$，它对答案的贡献为$min(lcnt[x],rcnt[x])$，把这些$x$的贡献都累加起来就是答案。

复杂度分析

时间复杂度

遍历了$n$个字符串一次，对于每个字符串，需要遍历它的每个字符，而字符串长度的总和也是$O(n)$的，因此遍历的时间复杂度为$O(n)$。

之后要遍历哈希表$lcnt$，对每个$key$都要检查其是否也在$rcnt$中，从而计算最大配对数。在最差情况下每个字符串的左括号净含量都不同，有$O(n)$级别的$key$数量，因此遍历的时间复杂度为$O(n)$。

综上，整个算法的时间复杂度为$O(n)$。

空间复杂度

开辟了$lcnt$和$rcnt$两个哈希表的空间，在最差情况下这两个哈希表会存$O(n)$级别的键值对，因此算法整体的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
int n;

int main() {
    scanf("%d", &n);
    int zcnt = 0;
    unordered_map<int, int> lcnt, rcnt;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int left = 0, right = 0;
        for(char c: s) {
            if(c == '(') {
                left++;
            }else {
                if(left > 0) {
                    left--;
                }else {
                    right++;
                }
            }
        }
        if(left > 0 && right > 0) continue;
        if(left > 0) {
            lcnt[left]++;
        }else if(right > 0) {
            rcnt[right]++;
        }else {
            zcnt++;
        }
    }
    int ans = zcnt>>1;
    for(auto&[k, v]: lcnt) {
        if(rcnt.find(k) != rcnt.end()) {
            ans += min(v, rcnt[k]);
        }
    }
    printf("%d\n", ans);
    return 0;
}