Question

1963. Minimum Number of Swaps to Make the String Balanced

中文文档

Description

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

• It is the empty string, or
• It can be written as AB, where both A and B are balanced strings, or
• It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return _the minimum number of swaps to make _s _balanced_.

 

Example 1:

Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".

Example 2:

Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".

Example 3:

Input: s = "[]"
Output: 0
Explanation: The string is already balanced.

 

Constraints:

• n == s.length
• 2 <= n <= 106
• n is even.
• s[i] is either '['or ']'.
• The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.

Solutions

Solution 1: Greedy

We use a variable $x$ to record the current number of unmatched left brackets. We traverse the string $s$, for each character $c$:

• If $c$ is a left bracket, then we increment $x$ by one;
• If $c$ is a right bracket, then we need to check whether $x$ is greater than zero. If it is, we match the current right bracket with the nearest unmatched left bracket on the left, i.e., decrement $x$ by one.

After the traversal, we will definitely get a string of the form "]]]...[[[...". We then greedily swap the brackets at both ends each time, which can eliminate $2$ unmatched left brackets at a time. Therefore, the total number of swaps needed is $\left\lfloor \frac{x + 1}{2} \right\rfloor$.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.

class Solution:
  def minSwaps(self, s: str) -> int:
    x = 0
    for c in s:
      if c == "[":
        x += 1
      elif x:
        x -= 1
    return (x + 1) >> 1

class Solution {
  public int minSwaps(String s) {
    int x = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (c == '[') {
        ++x;
      } else if (x > 0) {
        --x;
      }
    }
    return (x + 1) / 2;
  }
}

class Solution {
public:
  int minSwaps(string s) {
    int x = 0;
    for (char& c : s) {
      if (c == '[') {
        ++x;
      } else if (x) {
        --x;
      }
    }
    return (x + 1) / 2;
  }
};

func minSwaps(s string) int {
  x := 0
  for _, c := range s {
    if c == '[' {
      x++
    } else if x > 0 {
      x--
    }
  }
  return (x + 1) / 2
}

function minSwaps(s: string): number {
  let x = 0;
  for (const c of s) {
    if (c === '[') {
      ++x;
    } else if (x) {
      --x;
    }
  }
  return (x + 1) >> 1;
}