Minimum Number of Swaps to Make the String Balanced #12 Most Asked

Medium

2 views

Topics:

StringsTwo PointersStacksGreedy Algorithms

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.

Try coding it in LeetCode

Minimum Number of Swaps to Make the String Balanced #12 Most Asked

Medium

Twilio

2 views

Topics:

StringsTwo PointersStacksGreedy Algorithms

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`?
If the string cannot be balanced with any number of swaps, what should I return?
Can the input string `s` be empty or null?
Is the input string guaranteed to only contain '[' and ']' characters, or could there be other characters?
If multiple solutions exist with the same minimum number of swaps, is any one of them acceptable?

Brute Force Solution

Approach

The brute force approach is like trying every possible arrangement of the string, swapping characters in all sorts of combinations. We'll check each of these arrangements to see if it's balanced and keep track of the best result.

Here's how the algorithm would work step-by-step:

Start by looking at the original string as our first possible arrangement.
Then, try swapping two characters in the string, creating a new arrangement.
Repeat this swapping process for every possible pair of characters in the string, generating many different arrangements.
For each arrangement we create, check if it is balanced (meaning the number of opening brackets matches the number of closing brackets and they are in the right order).
If an arrangement is balanced, count how many swaps it took to get to that arrangement from the original string.
Keep track of the arrangement that's balanced and needed the fewest swaps.
Continue this process, exploring more and more swaps, until we've tried enough combinations (or until we're convinced we've found the absolute minimum number of swaps).
Finally, the minimum number of swaps we found is the answer.

Code Implementation

def minimum_swaps_brute_force(unbalanced_string):
    minimum_number_of_swaps = float('inf')
    string_length = len(unbalanced_string)

    def is_balanced(input_string):
        balance = 0
        for character in input_string:
            if character == '[':
                balance += 1
            else:
                balance -= 1
            if balance < 0:
                return False
        return balance == 0

    def solve(current_string, swap_count):
        nonlocal minimum_number_of_swaps

        if is_balanced(current_string):
            minimum_number_of_swaps = min(
                minimum_number_of_swaps, swap_count)
            return

        # Optimization:
        # Stop searching when swaps exceeds best known
        if swap_count >= minimum_number_of_swaps:
            return

        for first_index in range(string_length):
            for second_index in range(
                    first_index + 1, string_length):

                string_list = list(current_string)

                # Create a new string arrangement by swapping
                string_list[first_index], string_list[second_index] = \
                    string_list[second_index], string_list[first_index]

                new_string = "".join(string_list)
                
                # Recursively check this arrangement
                solve(new_string, swap_count + 1)

    # Begin searching with original string
    solve(unbalanced_string, 0)

    # If no solution, return -1
    if minimum_number_of_swaps == float('inf'):
        return -1

    return minimum_number_of_swaps

Big(O) Analysis

Time Complexity

O((n!)*n) – The algorithm explores all possible arrangements of the string of length n, which leads to n! permutations. For each permutation, it checks if the string is balanced, which requires traversing the string of length n. Therefore, the time complexity is O((n!)*n).

Space Complexity

O(N!) – The brute force approach, as described, explores all possible arrangements of the string by swapping characters. To generate these arrangements, it implicitly creates copies of the string at each step of swapping. In the worst case, it may need to store all possible permutations, which is N! where N is the length of the string. Therefore, the auxiliary space used to store these permutations is proportional to N!.

Optimal Solution

Approach

The key insight is to count how many brackets are out of place. We then realize that we can fix two misplaced brackets with a single swap. Therefore we determine the answer by dividing the number of misplaced brackets by two.

Here's how the algorithm would work step-by-step:

First, think about what a balanced string of brackets looks like. It should have the same number of opening and closing brackets, and for every opening bracket, there's a corresponding closing bracket later in the string.
Now, go through the given string of brackets from left to right, keeping track of how 'unbalanced' things are. Every time you see a closing bracket when you need an opening bracket, or vice versa, it means something is out of place.
More specifically, we want to count the number of closing brackets that appear before where they should. Meaning the number of closing brackets that are on the 'left' side of the string where opening brackets are supposed to be.
The minimum number of swaps needed is half the number of these misplaced closing brackets. Since one swap can correct the position of two misplaced brackets.
If the number of misplaced brackets is odd, round the result up to the next whole number, because you can't have half a swap. Though in this case, the number of misplaced brackets will always be even.

Code Implementation

def minimum_swaps(brackets_string):
    mismatched_closing_brackets = 0
    opening_bracket_count = 0

    for bracket in brackets_string:
        if bracket == '[':
            opening_bracket_count += 1
        else:
            # Count misplaced closing brackets
            if opening_bracket_count > 0:
                opening_bracket_count -= 1
            else:
                mismatched_closing_brackets += 1

    # Each swap corrects two misplaced brackets
    minimum_number_of_swaps = (mismatched_closing_brackets + 1) // 2

    return minimum_number_of_swaps

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once to count the number of misplaced closing brackets. The cost of each operation within the loop (incrementing a counter, comparing characters) is constant. Therefore, the time complexity is directly proportional to the length of the string, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm iterates through the input string but does not create any auxiliary data structures that scale with the size of the input string, denoted as N. It primarily uses a counter to track the imbalance between opening and closing brackets. Therefore, the space required remains constant regardless of the input string's length.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 because an empty string is already balanced or throw an IllegalArgumentException depending on problem specifics.
String with odd length	Return -1 because a balanced string requires equal number of '[' and ']' characters and an odd length cannot satisfy this condition.
String with only '[' or only ']' characters	Calculate the number of swaps needed based on string length / 2, as that's how many characters must be swapped.
String is already balanced	Return 0 because no swaps are needed.
Maximum-sized input string to assess scalability.	The solution should use an efficient algorithm (e.g., O(n) time complexity) to avoid exceeding time limit for large inputs.
String starts with all ']' characters followed by all '[' characters	This represents the worst-case scenario needing maximum swaps; verify correctness in this case.
String contains a prefix where the number of ']' exceeds the number of '[' characters	The algorithm should identify and correct these imbalances, incrementing the swap count accordingly.
String contains many localized imbalances (e.g., '][][][')	The solution must handle multiple local imbalances efficiently to determine the minimum swaps required.

Null or empty input string

How to Handle:

Return 0 because an empty string is already balanced or throw an IllegalArgumentException depending on problem specifics.

String with odd length

How to Handle:

Return -1 because a balanced string requires equal number of '[' and ']' characters and an odd length cannot satisfy this condition.

String with only '[' or only ']' characters

How to Handle:

Calculate the number of swaps needed based on string length / 2, as that's how many characters must be swapped.

String is already balanced

How to Handle:

Return 0 because no swaps are needed.

Maximum-sized input string to assess scalability.

How to Handle:

The solution should use an efficient algorithm (e.g., O(n) time complexity) to avoid exceeding time limit for large inputs.

String starts with all ']' characters followed by all '[' characters

How to Handle:

This represents the worst-case scenario needing maximum swaps; verify correctness in this case.

String contains a prefix where the number of ']' exceeds the number of '[' characters

How to Handle:

The algorithm should identify and correct these imbalances, incrementing the swap count accordingly.

String contains many localized imbalances (e.g., '][][][')

How to Handle:

The solution must handle multiple local imbalances efficiently to determine the minimum swaps required.