Minimum Number of Swaps to Make the String Balanced solution and explanation
IBM
Google
9 more videos on this problem
Minimum Number of Swaps to Make String Balanced - Leetcode 1963 Weekly Contest - PythonNeetCode · 11:51 · 51K views
Minimum Number of Swaps to Make the String Balanced | Intuition | Leetcode 1963 | codestorywithMIKcodestorywithMIK · 18:09 · 15K views
Minimum Number of Swaps to Make the String Balanced | Leetcode 1963Techdose · 10:31 · 4K views
1963. Minimum Number of Swaps to Make the String Balanced (Leetcode Medium)Programming Live with Larry · 10:02 · 1K views
1963. Minimum Number of Swaps to Make the String Balanced | Leetcode Daily (POTD) 8 Oct 2024 | JavaAlgorithmHQ · 9:10 · 1K views
LeetCode | 1963. Minimum Number of Swaps to Make the String Balanced | Two PointerCompl3x · 12:20 · 861 views
LeetCode 1963. Minimum Number of Swaps to Make the String Balanced | PythonLea's coding · 3:26 · 576 views
Daily Leetcode #1652: Oct 08, 2024 - 1963. Minimum Number of Swaps to Make the String BalancedProgramming Live with Larry · 8:07 · 513 views
Leetcode 1963 - Simple solution - Minimum Number of Swaps to Make the String BalancedRikam Palkar · 1:26 · 218 views
Minimum Number of Swaps to Make the String Balanced - LeetCode 1963 - PythonAlpha-Code · 9:10 · 196 views
The problem
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 bothAandBare balanced strings, or - It can be written as
[C], whereCis 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.length2 <= n <= 106nis even.s[i]is either'['or']'.- The number of opening brackets
'['equalsn / 2, and the number of closing brackets']'equalsn / 2.
Approach overview
Problem Overview: You are given a string consisting only of '[' and ']'. The string contains equal numbers of both brackets but may be unbalanced. The goal is to compute the minimum number of swaps needed to transform it into a valid balanced bracket sequence.
Approach 1: Greedy Using Balance Count (O(n) time, O(1) space)
This approach scans the string once while tracking the current bracket balance. Increment the balance for '[' and decrement for ']'. When the balance becomes negative, it means a closing bracket appears before a matching opening bracket. At that point you conceptually perform a swap with a future '['. Each time this happens, increase the swap counter and reset the balance to 1 because the swap effectively inserts a valid opening bracket before the closing one.
The key insight is that you never need to physically perform swaps. Counting imbalance is enough because every time the prefix becomes invalid, one swap will fix it. This greedy logic works since each correction locally restores validity and guarantees the minimal number of swaps. The method runs in linear time and constant space and is the cleanest solution for this problem. This pattern commonly appears in greedy and string balancing problems.
Approach 2: Two-Pointer Swap Simulation (O(n) time, O(1) space)
The two-pointer strategy simulates the swaps explicitly. Maintain a left pointer scanning for imbalance and a right pointer searching for the next available '[' that can fix it. When the prefix becomes invalid (more ']' than '['), move the right pointer backward until a '[' is found and swap it with the problematic closing bracket.
This technique directly demonstrates why each imbalance requires a swap. After the swap, continue scanning from the left while maintaining the balance count. The algorithm still runs in O(n) time because each pointer moves at most once across the string. This approach is useful for understanding the mechanics of fixing invalid bracket sequences and often appears in problems using two pointers or stack-like validation logic.
Recommended for interviews: The greedy balance-count approach is what interviewers usually expect. It shows you recognize the imbalance pattern and can solve it with a single pass and constant memory. Demonstrating the two-pointer simulation first can help explain the intuition, but the greedy counting method highlights stronger algorithmic insight.
Approach 1: Greedy Approach Using Balance Count
This approach involves traversing the string and counting the balance between opening and closing brackets. You increase a count when you find an opening bracket and decrease the count when you find a closing bracket. If at any point the count goes negative, a swap is needed to balance out the string, and the swap count is incremented. The final swap count will be the required number of swaps to make the string balanced.
def min_swaps(s):
balance = 0
swaps = 0
for ch in s:
balance += 1 if ch == '[' else -1
if balance < 0:
swaps += 1
balance += 2
return swaps
s = "][]["
print("Minimum swaps:", min_swaps(s))public class MinSwaps {
public static int minSwaps(String s) {
int balance = 0, swaps = 0;
for (char ch : s.toCharArray()) {
balance += (ch == '[') ? 1 : -1;
if (balance < 0) {
swaps++;
balance += 2;
}
}
return swaps;
}
public static void main(String[] args) {
String s = "][][";
System.out.println("Minimum swaps: " + minSwaps(s));
}
}#include <iostream>
#include <string>
int minSwaps(const std::string &s) {
int balance = 0, swaps = 0;
for (char ch : s) {
balance += (ch == '[') ? 1 : -1;
if (balance < 0) {
swaps++;
balance += 2;
}
}
return swaps;
}
int main() {
std::string s = "][][";
std::cout << "Minimum swaps: " << minSwaps(s) << std::endl;
return 0;
}function minSwaps(s) {
let balance = 0, swaps = 0;
for (const ch of s) {
balance += (ch === '[') ? 1 : -1;
if (balance < 0) {
swaps++;
balance += 2;
}
}
return swaps;
}
const s = '][[';
console.log('Minimum swaps:', minSwaps(s));#include <stdio.h>
#include <string.h>
int minSwaps(char *s) {
int balance = 0, swaps = 0;
for (int i = 0; i < strlen(s); i++) {
if (s[i] == '[') {
balance++;
} else {
balance--;
}
if (balance < 0) {
swaps++;
balance += 2;
}
}
return swaps;
}
int main() {
char s[] = "][][";
printf("Minimum swaps: %d\n", minSwaps(s));
return 0;
}using System;
public class MinSwaps {
public static int MinSwapsToBalance(string s) {
int balance = 0, swaps = 0;
foreach (char ch in s) {
balance += (ch == '[') ? 1 : -1;
if (balance < 0) {
swaps++;
balance += 2;
}
}
return swaps;
}
public static void Main(string[] args) {
string s = "][][";
Console.WriteLine("Minimum swaps: " + MinSwapsToBalance(s));
}
}The Python function loops over the string, updating the balance and counting swaps whenever the balance indicates an excess closing bracket.
Time Complexity: O(n), where n is the length of string s.
Space Complexity: O(1), since it uses constant additional space.
Approach 2: Two-Pointer Approach
This approach uses two pointers to traverse the string efficiently. One pointer starts from the beginning of the string, and the other starts at the end. Using these pointers, swaps are performed when an excessive number of closing brackets on one side can be paired with an opening bracket on the other side.
def min_swaps(s):
left, right = 0, len(s) - 1
swaps = 0
while left < right:
if s[left] == '[':
left += 1
elif s[right] == ']':
right -= 1
else:
swaps += 1
left += 1
right -= 1
return swaps
s = "][]["
print("Minimum swaps:", min_swaps(s))public class MinSwaps {
public static int minSwaps(String s) {
int left = 0, right = s.length() - 1, swaps = 0;
while (left < right) {
if (s.charAt(left) == '[') {
left++;
} else if (s.charAt(right) == ']') {
right--;
} else {
swaps++;
left++;
right--;
}
}
return swaps;
}
public static void main(String[] args) {
String s = "][][";
System.out.println("Minimum swaps: " + minSwaps(s));
}
}#include <iostream>
#include <string>
int minSwaps(const std::string &s) {
int left = 0, right = s.size() - 1, swaps = 0;
while (left < right) {
if (s[left] == '[') {
left++;
} else if (s[right] == ']') {
right--;
} else {
swaps++;
left++;
right--;
}
}
return swaps;
}
int main() {
std::string s = "][][";
std::cout << "Minimum swaps: " << minSwaps(s) << std::endl;
return 0;
}function minSwaps(s) {
let left = 0, right = s.length - 1;
let swaps = 0;
while (left < right) {
if (s[left] === '[') {
left++;
} else if (s[right] === ']') {
right--;
} else {
swaps++;
left++;
right--;
}
}
return swaps;
}
const s = '][[';
console.log('Minimum swaps:', minSwaps(s));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int minSwaps(char *s) {
int left = 0, right = strlen(s) - 1, swaps = 0;
int balance = 0;
while (left < right) {
if(s[left] == '[') {
balance++;
left++;
} else if(s[right] == ']') {
balance--;
right--;
} else {
swaps++;
left++;
right--;
balance = 0;
}
}
return swaps;
}
int main() {
char s[] = "][][";
printf("Minimum swaps: %d\n", minSwaps(s));
return 0;
}using System;
public class MinSwaps {
public static int MinSwapsToBalance(string s) {
int left = 0, right = s.Length - 1, swaps = 0;
while (left < right) {
if (s[left] == '[') {
left++;
} else if (s[right] == ']') {
right--;
} else {
swaps++;
left++;
right--;
}
}
return swaps;
}
public static void Main(string[] args) {
string s = "][][";
Console.WriteLine("Minimum swaps: " + MinSwapsToBalance(s));
}
}Python's version applies a method operating directly with start and end pointers, handling misbalanced parentheses in a way such as identifiers swap when unfavorable brackets are met, returning the minimum number of swaps needed.
Time Complexity: O(n), from one complete string scan.
Space Complexity: O(1), since anciliary storage is minimal.
Approach 3: Greedy
We use a variable x to record the current number of unmatched left brackets. We traverse the string s, for each character c:
- If
cis a left bracket, then we incrementxby one; - If
cis a right bracket, then we need to check whetherxis greater than zero. If it is, we match the current right bracket with the nearest unmatched left bracket on the left, i.e., decrementxby one.
After the traversal, we will definitely get a string of the form "]]]...[[[...". We then greedily swap the brackets at both ends each time, which can eliminate 2 unmatched left brackets at a time. Therefore, the total number of swaps needed is \left\lfloor \frac{x + 1}{2} \right\rfloor.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function minSwaps(s: string): number {
let x = 0;
for (const c of s) {
if (c === '[') {
++x;
} else if (x) {
--x;
}
}
return (x + 1) >> 1;
}func minSwaps(s string) int {
x := 0
for _, c := range s {
if c == '[' {
x++
} else if x > 0 {
x--
}
}
return (x + 1) / 2
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Balance Count | Time Complexity: O(n), where n is the length of string s. |
| Two-Pointer Approach | Time Complexity: O(n), from one complete string scan. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Using Balance Count | O(n) | O(1) | Best general solution; minimal logic and optimal complexity |
| Two-Pointer Swap Simulation | O(n) | O(1) | Useful for understanding how swaps fix imbalance step by step |
Frequently asked questions
Is Minimum Number of Swaps to Make the String Balanced easy or hard?
The problem is rated Medium because the logic requires recognizing the imbalance pattern rather than performing literal swaps. Once the greedy observation is clear, the implementation becomes straightforward with a single pass and constant memory.
Minimum Number of Swaps to Make the String Balanced Python/Java solution
Most implementations follow the same logic: iterate through the string, update the balance counter, and count swaps when the balance becomes negative. The algorithm is short and works identically in Python, Java, C++, C#, and JavaScript because it relies only on simple counters.
How to solve Minimum Number of Swaps to Make the String Balanced in O(n)?
Iterate through the string and maintain a balance counter. Increase it for '[' and decrease it for ']'. If the balance becomes negative, it means a closing bracket appears too early, so increment the swap count and reset the balance to 1 to simulate swapping with a future '['. Continue until the end of the string.
What is the best approach for Minimum Number of Swaps to Make the String Balanced?
The greedy balance counting approach is the most efficient solution. Scan the string once while tracking the difference between opening and closing brackets. Whenever the balance becomes negative, increment the swap counter and reset the balance to reflect the conceptual swap. This runs in O(n) time with O(1) space.
Is Minimum Number of Swaps to Make the String Balanced asked at Google/Amazon/Meta?
Bracket balancing and swap minimization problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this question test understanding of greedy logic, stack behavior, and string processing in linear time.
What data structure is used in Minimum Number of Swaps to Make the String Balanced?
The optimal approach does not require complex data structures. A simple integer balance counter is enough to track unmatched brackets. Conceptually the problem relates to stack-based bracket validation, but the greedy method eliminates the need for an actual stack.
What is the time complexity of Minimum Number of Swaps to Make the String Balanced?
The optimal solution runs in O(n) time because the string is scanned once. Only a few integer counters are maintained, so the space complexity is O(1). Even the two-pointer simulation version remains linear because each pointer moves across the string at most once.