通过交换来平衡括号

Question

我有一个包含字符 ( 和 ) 的字符串，例如 )()(())(。请找出使其平衡所需的最小交换次数。我们可以交换任意字符，它们不需要相邻。如果无法达到平衡，则返回 -1。

对于示例 )()(())(，我们可以通过交换第一个和最后一个字符将其变成平衡字符串 (()(()))，所以交换次数为 1，答案是 1。

字符串的长度范围为 1 到 10⁵

这是我的代码：

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;
}

上述方法在时间复杂度上不够高效。请问如何用更少的时间复杂度来解决这个问题？

Brad Christie · Answer

我在此补充了一个示例代码：

public class MinSwaps {
    public static int solve(String s) {
        int opens = 0;
        int closes = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                opens++;
            } else {
                if(opens > 0) opens--;
                else closes++;
            }
        }

        if(opens == closes) return opens;
        return -1;

    }
    public static void main(String[] args) {
        String input = ")()(())(";
        int result = solve(input);
        System.out.println("Minimum swaps needed: " + result);
    }
}

在该代码中：

opens：表示在遍历过程中遇到的未匹配左括号的数量。
closes：表示在遍历过程中遇到的未匹配右括号的数量。

这两个变量用于在遍历输入字符串时跟踪未匹配的括号。

如果未匹配的左括号数量与未匹配的右括号数量相等，函数将返回左括号数量；否则返回 -1。

对于示例 )()(())(，该函数会返回 1，表示存在 1 对未匹配的左括号和右括号。

UnkwnTech · Answer

I am using a Stack to keep track of the open pairs:

import java.util.Stack;  

public class MyClass {

    public static int solve(String s) {

        Stack<Character> st = new Stack<Character>();

        int opens = 0;

        int closes = 0;
        

    for (char c : s.toCharArray()) {
        if (c == '(') {
            //  open a pair to be resolved
            st.push(c);
            opens++;
        } else {
            if (st.empty() || (st.peek() == ')')) {
                //  can't resolve, have to store
                st.push(c);
                closes++;
            } else {
                //  resolve one pair
                st.pop();
                opens--;
            }
        }
    }

    if (opens == closes) {
        return opens;
    }
    
    return -1;
}

public static void main(String[] args) {
    String input = ")()(";
    int result = solve(input);
    
    if (result == -1) {
        System.out.println("swapping not feasible");
    } else if (result == 0) {
        System.out.println("brackets are balanced");
    } else {
        System.out.println("Minimum swaps needed: " + result);
    }
}
}

Leo Dabus · Answer

一个有用的观察是，当左括号和右括号的数量相等时，总存在一种解决方案。

其次，当存在解决方案时，我们只需要计算没有对应左括号的右括号数量：这些右括号总是可以与字符串后面出现的任意左括号进行交换以形成有效序列。实际上无需找到那个左括号，也无需真正执行交换操作。

因此，一个有效的算法只需跟踪括号平衡状态，一旦平衡值变为负数（即遇到未匹配的右括号），就将其视为一次交换：

    public static int solve(String s) {
        int balance = 0;
        int numSwaps = 0;
        for (int i = 0; i < s.length(); i++) {
            balance += s.charAt(i) == '(' ? 1 : -1;
            if (balance < 0) { // 遇到未匹配的右括号
                balance = 0;
                numSwaps++;
            }
        }
        return balance == numSwaps ? numSwaps : -1;
    }