2095. Minimum Number Of Swaps To Make The String Balanced¶

Difficulty: Medium

2095. Minimum Number of Swaps to Make the String Balanced

Medium

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.

Example 1:

Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".

Example 2:

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

Example 3:

Input: s = "[]"
Output: 0
Explanation: The 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¶

class Solution {
    public int minSwaps(String s) {
        int n = s.length(), count = 0;
        Stack<Character> st = new Stack<>();
        for(int i = 0; i < n; i++) {
            char current = s.charAt(i);
            if (current == '[') st.add(current);
            else {
                if (st.size() == 0) count++;
                else st.pop();
            }
        }
        int ans = count / 2;
        if (count % 2 == 1) ans++;
        return ans;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here