1963. Minimum Number of Swaps to Make the String Balanced

#using stack
class Solution:
    def minSwaps(self, s: str) -> int:
        st=[]
        for i in s:
            if i=='[':#only store op bracks
                st.append(i)
            else:
                if st:st.pop()
        n=len(st)
        return n//2+n%2#e.g. ]][[,][
#without stack
class Solution:
    def minSwaps(self, s: str) -> int:
        ans=0
        c=0
        for i in s:
            c=c+1 if i=='[' else c-1
            if c<0:
                ans+=1
                c=1
        return ans
'''
Here we are maintaining the value c which pairs out brackets.
But whenever we see unpaired ] i.e. c<0 at any instance then we might have to take a '[' and swap with . Lets say there is a '[' some where and you swapped here(assume). Now c has to become 1 to match some upcoming ].
return the swaps
'''
#Method2:
   '''
   The idea is to traverse our string and check the biggest possible disbalance. For example if we look at ]]][]]][[[[[, for traversals we have:
-1, -2, -3, -2, -3, -4, -5, -4, -3, -2, -1, 0 and the biggest disbalance is equal to 5. What we can do in one swap of brackets is to decreas it at most by 2: for this we need to take the leftest ] with negative balance and the rightest [ with negative balance and change them. For example in our case we have:

[]][]]][[[[] : [1, 0, -1, 0, -1, -2, -3, -2, -1, 0, 1, 0]

[][[]]][][[] : [1, 0, 1, 2, 1, 0, -1, 0, -1, 0, 1, 0]

[][[]][[]][] : [1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 0]

Complexity

Time complexity is O(n) to traverse our string, space is O(1).
   '''
class Solution:
    def minSwaps(self, s):
        bal, ans = 0, 0
        for symb in s:
            if symb == "[": bal += 1
            else: bal -= 1
            ans = min(bal, ans)
        return (-ans + 1)//2