Leetcode 1963: Minimum Number of Swaps to Make the String Balanced

Input: The input consists of a string `s` of even length `n` consisting only of the characters `[` and `]`.

Example: s = "][]["

Constraints:

• 2 <= n <= 10^6

• s[i] is either '[' or ']'

• The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.

Output: Return the minimum number of swaps required to make the string balanced.

Example: Output: 1

Constraints:

• The output must be a single integer representing the minimum number of swaps.

Goal: The goal is to minimize the number of swaps by calculating how many unbalanced opening and closing brackets there are in the string.

Steps:

• Step 1: Iterate through the string and use a stack to track unmatched opening brackets.

• Step 2: Whenever a closing bracket is found, check if there is an unmatched opening bracket to pair it with.

• Step 3: Count the number of unmatched opening brackets and compute the necessary swaps.

Goal: The constraints ensure the problem is solvable within the input limits.

Steps:

• The input string contains only brackets and is of even length.

• The number of opening and closing brackets are equal.

Assumptions:

• The input string will always contain an equal number of opening and closing brackets.

• Input: Input: s = '][][', Output: 1

• Explanation: In this example, the first closing bracket `]` needs to be swapped with the last opening bracket `[`. After the swap, the string becomes balanced.

• Input: Input: s = ']]][[[', Output: 2

• Explanation: In this case, we need two swaps to balance the string. First, swap the 1st and 4th brackets, then swap the 2nd and 5th.

Approach: The problem can be solved by using a stack to manage unmatched opening brackets and keeping track of the number of swaps required.

Observations:

• We only need to handle unmatched brackets. Each unmatched closing bracket requires a corresponding opening bracket before it.

• Using a stack to simulate the process of pairing opening and closing brackets will allow us to efficiently compute the number of necessary swaps.

Steps:

• Step 1: Initialize an empty stack.

• Step 2: Iterate through the string, pushing the index of every opening bracket onto the stack.

• Step 3: When encountering a closing bracket, check if there is a matching opening bracket in the stack. If there is, pop the stack. If not, increment the count of swaps.

• Step 4: After the loop, calculate the number of unmatched opening brackets and return the result.

Empty Inputs:

• There will always be at least two brackets in the input string.

Large Inputs:

• Ensure that the solution handles the upper constraint of up to 10^6 brackets efficiently.

Special Values:

• If the string is already balanced, no swaps are needed.

Constraints:

• Handle all valid input cases where the string contains exactly equal numbers of opening and closing brackets.

int minSwaps(string s) {
    stack<char> stk;
    int n = s.length();
    for(int i = 0; i < n; i++) {
        if(s[i] == '[') stk.push(i);
        else if(!stk.empty()) stk.pop();
    }
    
    return (stk.size() + 1) / 2;
}

1 : Function Definition

int minSwaps(string s) {

The function `minSwaps` is defined, which takes a string `s` containing only '[' and ']' and calculates the minimum number of swaps to balance the string.

2 : Stack Initialization

    stack<char> stk;

A stack `stk` is initialized to help track unmatched '[' characters.

3 : String Length Calculation

    int n = s.length();

The length of the string `s` is stored in the variable `n`.

4 : Loop Through String

    for(int i = 0; i < n; i++) {

A loop begins to iterate through the string `s` from index 0 to `n-1`.

5 : Push to Stack

        if(s[i] == '[') stk.push(i);

If the current character is '[', its index is pushed onto the stack.

6 : Pop from Stack

        else if(!stk.empty()) stk.pop();

If the current character is ']' and the stack is not empty, the most recent unmatched '[' character is popped from the stack.

7 : Final Calculation

    return (stk.size() + 1) / 2;

The number of unmatched '[' characters left in the stack is used to calculate the minimum number of swaps. The formula `(stk.size() + 1) / 2` computes this.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: We process each character in the string exactly once, so the time complexity is linear in the size of the input string.

Best Case: O(n)

Worst Case: O(n)

Description: In the worst case, the stack will store all unmatched opening brackets, resulting in linear space complexity.

Leetcode 1963: Minimum Number of Swaps to Make the String Balanced

Explore →