Minimum Number of Swaps to Make the String Balanced

Leetcode Problem:

• Minimum Number of Swaps to Make the String Balanced

Summary

• The problem is to find the minimum number of swaps required to make a given string of even length balanced.

Approach

• The approach used is to use a stack data structure to keep track of the opening brackets
• The stack is used to check if a closing bracket matches with the top of the stack
• If a match is found, the top of the stack is popped
• If no match is found, the current bracket is pushed into the stack
• After processing the entire string, the minimum number of swaps required to balance the string is calculated by dividing the number of remaining opening brackets by 2 and adding 1, and then dividing by 2.

Complexity

• O(n) where n is the length of the string

Explanation

• The provided solution code uses a stack to keep track of the opening brackets
• The stack is initialized as a private member of the Solution class
• In the minSwaps function, the code iterates over the string and checks if the stack is empty
• If the stack is empty, the current character is pushed into the stack
• If the stack is not empty, the top of the stack is checked with the current character
• If they match, the top of the stack is popped
• If they do not match, the current character is pushed into the stack
• After processing the entire string, the minimum number of swaps required to balance the string is calculated by dividing the number of remaining opening brackets by 2 and adding 1, and then dividing by 2.

Solution Code:

struct _stack{
    char arr[1000001];
    int top;
    _stack(){
        top = 0;
    }
    void push(char a){
        arr[top++] = a;
    }
    bool empty(){
        return top == 0;
    }
    char peek(){
        if(empty()) return -1;
        return arr[top-1];
    }
    void pop(){
        if(empty()) return;
        top--;
    }
};

class Solution {
public:
    _stack st;
    int minSwaps(string s) {
        int res = 0;
        for(int i = 0 ; i < s.size(); i++){
            if(st.empty()){
                st.push(s[i]);
                continue;
            }
            char a = st.peek();
            char b = s[i];
            if(a == '[' && b == ']'){
                st.pop();
                continue;
            } else{
                st.push(b);
            }
        }
        return (st.top/2+1)/2;
    }
};