0387MediumTwo PointersStringStackGreedyBracket Sequences

Balance the Clamp Tape

Tracked in this browser only

Trains the technique from

LeetCode 1963Minimum Number of Swaps to Make the String Balanced

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_swaps(tape: str) -> int:

Java

public int minSwaps(String tape)

The intended approach

Time O(n)Space O(1)

Walk the tape once, keeping a count of `'['` marks that have not yet been closed. A `']'` that arrives with nothing waiting for it is stranded, and stranded marks are the only obstruction. One exchange takes a stranded `']'` from the front of the tape and a surplus `'['` from the back, which repairs two stranded marks at a time, so the answer is half the stranded count rounded up.

Pythonentry point: min_swaps

def min_swaps(tape):
    # Time O(n) -- one pass over the tape.
    # Space O(1) -- two counters.
    waiting = 0
    stranded = 0
    for mark in tape:
        if mark == "[":
            waiting += 1
        elif waiting:
            waiting -= 1
        else:
            stranded += 1
    return (stranded + 1) // 2

The obvious version

Simulate the repair. Find the leftmost mark at which the running depth first goes negative, exchange it with the last `'['` on the tape, count the exchange, and start the scan over. Quadratic, and it never reasons about counts.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_swaps(tape):
    marks = list(tape)
    swaps = 0
    while True:
        depth = 0
        bad = -1
        for i, mark in enumerate(marks):
            depth += 1 if mark == "[" else -1
            if depth < 0:
                bad = i
                break
        if bad < 0:
            return swaps
        j = len(marks) - 1
        while marks[j] != "[":
            j -= 1
        marks[bad], marks[j] = marks[j], marks[bad]
        swaps += 1

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in