通过交换平衡括号：求最小交换次数的高效解法

我有一个仅包含字符(和)的字符串，例如)()(())(，需要找出使其平衡所需的最小交换次数（可交换任意字符，无需相邻），若无法平衡则返回-1。示例中交换首尾字符可得到平衡字符串(()(()))，交换次数为1，答案为1。字符串长度范围为1 to 10^5。

以下是我最初的实现，但时间复杂度较高，想知道如何优化到更低的时间复杂度：

public static int solve(String s) {
  while(true) {
    int pos = s.indexOf("()");
    if(pos == -1) break;
    s = s.substring(0, pos) + s.substring(pos+2);
  }
  int open = 0, close = 0;
  for(char c : s.toCharArray()) {
    if(c == '(') open++;
    else close++;
  }
  if(open == close) return open;
  return -1;
}

原代码的问题分析 #

原代码通过反复查找并移除()子串来简化字符串，最后统计剩余的左右括号数量。但每次调用indexOf和substring都会生成新字符串，时间复杂度为O(n²)，对于长度1e5的字符串来说，这种方法会超时，完全无法处理大规模输入。

优化方案：O(n)时间复杂度解法 #

核心思路是通过一次遍历统计关键指标，无需修改原字符串：

1. 首先判断字符串长度是否为偶数——奇数长度的括号串不可能平衡，直接返回-1。
2. 遍历过程中维护balance（当前括号平衡度：(加1，)减1），同时记录无法匹配的右括号数量closeCount。
3. 遍历结束后，balance的值就是未匹配的左括号数量openCount，只有当openCount等于closeCount时，字符串才能被平衡。
4. 最小交换次数可以通过公式(openCount + 1) // 2计算：每一次交换最多能解决两个未匹配的括号（比如))((只需1次交换），向上取整除以2即可得到最小次数。

优化后的代码：

public static int minSwapsToBalance(String s) {
    int n = s.length();
    // 奇数长度直接返回-1
    if (n % 2 != 0) {
        return -1;
    }
    
    int balance = 0;
    int closeCount = 0;
    
    for (char c : s.toCharArray()) {
        if (c == '(') {
            balance++;
        } else {
            balance--;
        }
        
        // 遇到无法匹配的右括号，记录并重置平衡度
        if (balance < 0) {
            closeCount++;
            balance = 0;
        }
    }
    
    int openCount = balance;
    // 未匹配的左右括号数量不等，无法平衡
    if (openCount != closeCount) {
        return -1;
    }
    
    // 计算最小交换次数
    return (openCount + 1) / 2;
}

代码说明 #

• 时间复杂度O(n)：仅需一次遍历字符串，所有操作都是常数时间。
• 空间复杂度O(1)：只使用了几个整型变量，无需额外空间存储字符串或其他结构。
• 测试示例)()(())(：遍历后closeCount=1，openCount=1，计算得(1+1)/2=1，与预期结果一致。
• 测试示例))((：遍历后closeCount=2，openCount=2，计算得(2+1)/2=1，符合实际需求。

内容的提问来源于stack exchange，提问作者Learner