Minimum Number of Swaps to Make the String Balanced

Medium
401.

Minimum Number of Swaps to Make the String Balanced

Minimum Number of Swaps to Make the String Balanced is a medium coding problem on strings, greedy and two pointers, asked in Amazon and Google interviews.

You are given a string s of even length containing exactly n/2 opening brackets '[' and n/2 closing brackets ']'.

In one move you may swap any two characters. Return the minimum number of swaps needed to make the string balanced.

Example 1

Input
s = "][]["
Output
1

Example 2

Input
s = "]]][[["
Output
2

Example 3

Input
s = "[]"
Output
0

Constraints

  • 2 <= s.length <= 40
  • s.length is even.
  • s contains equally many '[' and ']'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Swaps to Make the String Balanced Solution

Minimum Number of Swaps to Make the String Balanced solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Swaps to Make the String Balanced is a medium coding problem on strings, greedy and two pointers, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy, Two Pointers, Stack
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s of even length containing exactly n/2 opening brackets '[' and n/2 closing brackets ']'.

In one move you may swap any two characters. Return the minimum number of swaps needed to make the string balanced.

Example 1

Input: s = "][]["
Output: 1

Example 2

Input: s = "]]][[["
Output: 2

Example 3

Input: s = "[]"
Output: 0

Constraints

  • 2 <= s.length <= 40
  • s.length is even.
  • s contains equally many '[' and ']'.

Hints for Minimum Number of Swaps to Make the String Balanced

  1. Hint 1

    Cancel matched pairs as you scan; what remains is a block of ] followed by a block of [, of equal size.

  2. Hint 2

    One well-chosen swap fixes two of the unmatched pairs at once.

  3. Hint 3

    So the answer is the number of unmatched pairs, rounded up after halving.

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

Cancel matched pairs; what remains is ]]…[[ with u unmatched of each, and one swap fixes two of them, so the answer is ⌈u / 2⌉.

Approach

  1. Scan counting unmatched [; a ] cancels one if available.
  2. Return (unmatched + 1) // 2.

Why it works

After cancelling, the leftover is u closers followed by u openers; swapping the first ] with the last [ balances two pairs at once, and no swap can fix more than two.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • The count of unmatched ] equals the count of unmatched [ because the totals are equal.

Reference solution

Python

def minSwaps(s: str) -> int:
    unmatched = 0
    for ch in s:
        if ch == "[":
            unmatched += 1
        elif unmatched > 0:
            unmatched -= 1
    return (unmatched + 1) // 2

Java

public static int minSwaps(String s) {
    int unmatched = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '[') unmatched++;
        else if (unmatched > 0) unmatched--;
    }
    return (unmatched + 1) / 2;
}

C++

int minSwaps(string s) {
    int unmatched = 0;
    for (char c : s) {
        if (c == '[') unmatched++;
        else if (unmatched > 0) unmatched--;
    }
    return (unmatched + 1) / 2;
}

JavaScript

var minSwaps = function(s) {
    let unmatched = 0;
    for (let i = 0; i < s.length; i++) {
        if (s.charAt(i) === "[") unmatched++;
        else if (unmatched > 0) unmatched--;
    }
    return Math.floor((unmatched + 1) / 2);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms