Minimum Number Of Swaps To Make The String Balanced - Leetcode Solution

Problem: Given a string with only characters ‘[’ and ‘]’, we have to find the minimum number of swaps required to make the string balanced. A string is considered balanced if it consists of alternating brackets, such as “[[]]” or “[][[]]”.

Approach: To solve this problem we can use stack data structure. We need to traverse the string from left to right and for every opening bracket, we push its index onto the stack. If we encounter a closing bracket, we check if the stack is not empty and if the top of the stack is an opening bracket of the same type. If it is, we pop the opening bracket from the stack, and the current closing bracket is paired with it, otherwise, we push the index of the current closing bracket onto the stack. Once we have processed the whole string, the stack should only contain the indices of unmatched opening brackets.

Now, to make the given string balanced, we need to swap the unmatched opening brackets with unmatched closing brackets. We can calculate the number of unmatched opening and closing brackets using the stack size and return half of it as the minimum number of swaps required.

Code:

def min_swaps_to_balance(s: str) -> int:
    stack = []
    for i, c in enumerate(s):
        if c == '[':
            stack.append(i)
        else:
            if stack and s[stack[-1]] == '[':
                stack.pop()
            else:
                stack.append(i)

    return len(stack) // 2

Time Complexity: O(n) where n is the length of the given string.

Space Complexity: O(n) as we are using a stack to store the indices.

1