1963. Minimum Number of Swaps to Make the String Balanced

Minimum Number of Swaps to Make the String Balanced (LeetCode 1963) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.

How to solve Minimum Number of Swaps to Make the String Balanced

Minimum Number of Swaps to Make the String Balanced is a Valid Parentheses problem, part of Stack Patterns. Master parentheses validation and balancing using stack. Handle multiple bracket types and minimum additions.

Work towards the solution in these steps:

1. Iterate over the string and keep track of the number of opening and closing brackets on each step.
2. If the number of closing brackets is ever larger, you need to make a swap.
3. Swap it with the opening bracket closest to the end of s.

The reference solution runs in O(n) time and O(1) space.

The Minimum Number of Swaps to Make the String Balanced solution and editorial walks through the full approach with reference code.

Problem statement

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 <= 106

- 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.

Topics and companies

Topics: Two Pointers, String, Stack, Greedy.

How to practise Minimum Number of Swaps to Make the String Balanced on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Minimum Number of Swaps to Make the String Balanced in the code editor, or read the Minimum Number of Swaps to Make the String Balanced editorial for a worked solution with its approach and complexity analysis.

Where Minimum Number of Swaps to Make the String Balanced sits in the DSA pattern sheet

• Stack Patterns pattern guide
• Valid Parentheses Matching subpattern
• The full DSA patterns sheet

Problems related to Minimum Number of Swaps to Make the String Balanced

Other problems that use the same Valid Parentheses Matching and Stack Patterns techniques:

• Longest Valid Parentheses — Hard, same subpattern
• Minimum Add to Make Parentheses Valid — Medium, same subpattern
• Minimum Remove to Make Valid Parentheses — Medium, same subpattern
• Valid Parentheses — Easy, same subpattern
• Valid Parenthesis String — Medium, same subpattern
• Asteroid Collision — Medium, same pattern

Minimum Number of Swaps to Make the String Balanced FAQ