Strings - Minimum Number of Swaps to Make The String Balanced

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

It is the empty string, or
It can be written as AB, where both A and B are balanced strings, or
It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

Input: s = "][]["
Output: 1
Explanation: You can string balanced by swapping index 0 with index 3 and the resulting string will be [[]]

Input: s = "]]][[["
Output: 2
Explanation: You can do the following swaps to make the string balanced:
- Swap index 0 with 4, and the resulting string will be "[]][][".
- Swap index 1 with index 5, and the resulting string will be "[[][]]".

Input: s = "[]"
Output: 0
Explanation: Input string is already balanced.

Constraints:

n == s.length
2 <= n <= 10⁶
n is even
s[i] is either '[' or ']'
The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.

Solution 1 - Using a stack
Solution 2 - Keep track of opening brackets and closing brackets in a variable (Efficient solution)

In this approach, we are going to use a Stack to store opening bracket '[' from input string s, and then when we find a closing bracket ']' we will balance them and no swapping is required, if the stack is empty, that means we will need a swap to make it balanced.

We will create a Stack to store opening brackets '[', and another variable swaps to track how many swaps are required.
Then, we will loop through characters of input string s and do the following:
- If the character is an opening bracket '[', then add to the stack.
- If the character if a closing bracket ']', then check if the stack is empty:
  1. If the stack is empty, that means a swap is needed, so we will increment the swaps by 1.
  2. If the stack is not empty, then we will take the top the element out from the stack to make opening bracket and closing brackets balanced.
Finally, return the total swaps required: (swaps + 1) /2, below are the reasons why we are doing +1 and divide by 2.
1. The division by 2 is because each swap operation addresses two unbalanced brackets. So, by counting the number of required swaps and then dividing that count by 2, it provides the actual number of unbalanced bracket pairs needing correction.
2. we are incrementing swaps count by 1 before divide by 2, to account for an edge case or a specific scenario where there might be an extra unbalanced bracket that requires attention.
  
  For instance, let's say the input string is ""]]]]][[[[[", it will give swaps = 5. If we do swaps /2 , it implies that 2 swaps are required to balance 4 unbalanced bracket pairs. If you adjust it to (swaps + 1) / 2, it would mean 3 unbalanced pairs plus one extra unbalanced bracket, needing 3 swaps in total.

Let's look at an example, say if the input string is "]]][[["

In the first step, we will initialize an empty stack and a variable swaps, to keep track os how may swaps are needed. Then will loop through the characters of input string s.
1^st character in the input string is ], so we will check whether stack is empty, since it is empty we will increment swaps to 1.
2^nd character in the input string is ], so we will check whether stack is empty, since it is empty we will increment swaps to 2.
3^rd character in the input string is ], so we will check whether stack is empty, since it is empty we will increment swaps to 3.
4^th character in the input string is [, so we will add it to stack.

stack

[
5^th character in the input string is [, so we will add it to stack.

stack

[

[

6^th character in the input string is [, so we will add it to stack.

stack
[
[
[

Now, we will return answer as (3 + 1) /2 = 2.
In this case input string s = "]]][[[" can be made to "[[][]]" with 2 swaps.
=> Swap 0^th index element ] with 4^th index element [, aftwr the swap it looks like this []][][
=> Swap 1^st index element ] with 5^th index element [, aftwr the swap it looks like this [[][]]

import java.util.Stack; public class MinSwapsToMakeStringBalanced { static int usingStack(String s) { Stack<Character> stack = new Stack<>(); int swaps = 0; for(char c : s.toCharArray()) { if(c == '[') { stack.push(c); } else { if(stack.isEmpty()) { // If the stack is empty, then a swap is needed swaps++; } else { stack.pop(); // Balance closing brackets with previous open bracket } } } return (swaps + 1)/2; // +1 to cover edge cases, where number of pairs to correct could be odd // divide by 2 is because each swap operation will correct two unbalanced brackets } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s
Space complexity: O(n) since we are storing opening brackets '[' in a stack.

This is similar to above solution, instead of storing the opening brackets in a stack, we will maintain them in a variable imbalanceCount.

public class MinSwapsToMakeStringBalanced { static int usingKeepingTrackOfClosingBrackets(String s) { int imbalanceCount = 0; int swaps = 0; for(char c: s.toCharArray()) { if(c == '[') { imbalanceCount++; } else { imbalanceCount--; } //If imbalanceCount is negative, make a swap to make it balance if(imbalanceCount <0){ swaps++; // Now, reset the count to 0, to continue imbalanceCount =0; } } return (swaps +1) /2; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s
Space complexity: O(1) since we are only two variables imbalanceCount to keep track of brackets and swaps variable to keep the count of swaps needed.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis:

Complexity Analysis: