What is the time complexity of LeetCode 1963. Minimum Number of Swaps to Make the String Balanced?

The Python solution on this page runs in O(n), where n is the length of the string s.

What is the space complexity of LeetCode 1963. Minimum Number of Swaps to Make the String Balanced?

The Python solution on this page uses O(1) auxiliary space.

Minimum Number of Swaps to Make the String Balanced — LeetCode 1963 Python Solution

MediumStackGreedyTwo PointersString

Problem: #1963
Pattern: Stack
Reading time: 2 min
Source: leetcode.com

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

Example

Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.

Python solution

Python

class Solution:
    def minSwaps(self, s: str) -> int:
        x = 0
        for c in s:
            if c == "[":
                x += 1
            elif x:
                x -= 1
        return (x + 1) >> 1

Complexity

Measure	Complexity
Time	O(n), where n is the length of the string s
Space	O(1) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 1963. Minimum Number of Swaps to Make the String Balanced is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1963. Minimum Number of Swaps to Make the String Balanced?: LeetCode 1963. Minimum Number of Swaps to Make the String Balanced is rated Medium on LeetCode.
What is the time complexity of LeetCode 1963. Minimum Number of Swaps to Make the String Balanced?: The Python solution on this page runs in O(n), where n is the length of the string s.
What is the space complexity of LeetCode 1963. Minimum Number of Swaps to Make the String Balanced?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1963. Minimum Number of Swaps to Make the String Balanced cover?: LeetCode 1963. Minimum Number of Swaps to Make the String Balanced is tagged Stack, Greedy, Two Pointers and String on LeetCode.