Minimum moves required to make string of bracket balanced

Question:

Calculate the minimum number of swaps necessary to make a string balanced

Logic:

1. Initialize sum = 0 to store the result.

2. Maintain a count of the number of ‘[‘ brackets encountered.

3. Reduce this count when encountering a ‘]’ character.

4. If the count becomes negative, we must start balancing the string.

5. Let index i represent the current position.

6. Move forward to the next ‘[‘ at index j.

7. Increase sum by j – i.

8. Swap the ‘[‘ at position j with the one at position i, shifting other characters to the right.

9. Set the count back to 1 and continue traversing the string.

Solution in python:

# Example usage s1 = “[]][][“ s2 = “[[][]]”

print(swapCount(s1)) # Output: 2

print(swapCount(s2)) # Output: 0

There are lot of sources are there when it comes to learning python. I will share if something is worth of sharing.. Stay tuned

Preparing for interview?

• Checkout our Interview prep page, It might help you.