Show problems as
Classic problem #1963MediumTwo PointersStringStackGreedyBracket Sequences

Minimum Number of Swaps to Make the String Balanced

Real-world version: Balance the Clamp Tape
Tracked in this browser only
Read Minimum Number of Swaps to Make the String Balanced on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A jig printer stamps a tape of clamp marks; tape records them as a string of '[' and ']' characters.

The tape is balanced when, reading from the left, the number of ']' marks seen never rises above the number of '[' marks seen, and the two counts are equal once the whole tape has been read.

In one operation you may exchange the marks at any two positions of the tape; the two positions need not be next to each other. Return the smallest number of operations that leaves tape balanced.

The tape has even length and carries as many '[' marks as ']' marks, so a balanced arrangement is always reachable.

Examples

Example 1

Input
tape = "]["
Output
1

Exchanging the two marks gives "[]", which is balanced.

Example 2

Input
tape = "]][["
Output
1

Exchanging position 0 with position 3 gives "[][]", which is balanced.

Example 3

Input
tape = "[]][[]"
Output
1

Exchanging position 2 with position 4 gives "[][][]", which is balanced.

Example 4

Input
tape = "[[]]"
Output
0

The tape is already balanced, so no exchange is needed.

Constraints

  • n == tape.length
  • 2 <= n <= 10^6
  • n is even.
  • tape[i] is either '[' or ']'.
  • tape holds exactly n / 2 marks of each kind.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_swaps(tape: str) -> int:
Java
public int minSwaps(String tape)

More on the same topics