# Daily Challenge 10/08/2024: Minimum Number of Swaps to Make the String Balanced

Compute the number of moves to balance a string of brackets.

The full problem may be found on leetcode.

## Analysis

### Example: Literal Swapping

The problem with this solution is that there must be a ledger of all unbalnced closing brackets and that on every iteration it must be checked if the string is balanced or not. This solution would have quadratic complexity.

```
][ requires one swap
]][[ requires one swap between 0 and 3
]]][[[ requires two swaps
- to get [[][]]
- between 0 and 5
- between 1 and 4
]]]][[[[
- to get [[]][[]]
- between 0 and 7 -> []]][[[] - between 1 and 6 -> [[]][[]]
```

```
closing = 0
opening = 0
]]]][[[[, too many closing, swap with last opening, closing = 1
^ *
[]]][[[], too many closing, swap with last opening, closing = 1
^ *
[[]][[]], too many closing, swap with last opening, closing = 1 ^ *
```

### Example: Counting

Another option is counting the number of unbalanced closing brackets:

```
]]]][[[[
^
unbalanced = 4, opening = 0
]]]][[[[
^
unbalanced = 4, opening = 1
]]]][[[[
^
unbalanced = 4, opening = 2
]]]][[[[
^
unblanced = 4, opening = 3
]]]][[[[
^ unbalanced = 4, opening = 4
```

Any unbalanced brackets swapping will balance two pairs. Therefore the number of swaps is `(unbalanced + 1) // 2`

- the plus 1 results in it being rounded up when `unbalanced`

is odd.

## Solution

This is a very strange problem - it is also not true that using a stack is necessary as described in the editorial. My solution beat \(78\%\) of solutions in runtime:

```
# stsart snippet solution
class Solution:
def minSwaps(self, s: str) -> int:
= 0
unbalanced = 0
opening
for char in s:
if char == "[":
+= 1
opening continue
if opening:
-= 1
opening else:
+= 1
unbalanced
return (unbalanced + 1) // 2
# end snippet solution
```