通过交换平衡支架

Question

我有一个包含字符

(

和

)

的字符串。例如

)()(())(

，找到使其平衡所需的最小交换量。我们可以交换任何字符，它们不必相邻。如果不可能返回-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;
}

就时间复杂度而言，这不是有效的方法。我们如何以更少的时间复杂度解决这个问题？

Answer 1

我在下面添加示例代码。

public class MinSwaps {
  public static int solve(String s) {
    int unmatchedOpenParentheses = 0, swaps = 0;

    for (char c : s.toCharArray()) {
      if (c == '(') unmatchedOpenParentheses++;
      else swaps += (unmatchedOpenParentheses > 0) ? unmatchedOpenParentheses-- : 1;
    }

    return unmatchedOpenParentheses + swaps;
}

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