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:

        unbalanced = 0
        opening = 0

        for char in s:
            if char == "[":
                opening += 1
                continue

            if opening:
                opening -= 1
            else:
                unbalanced += 1

        return (unbalanced + 1) // 2
        # end snippet solution