You are given a string S of 2N characters consisting of N ‘[‘ brackets and N ‘]’ brackets. A string is considered balanced if it can be represented in the form S2[S1] where S1 and S2 are balanced strings. We can make an unbalanced string balanced by swapping adjacent characters. 
Calculate the minimum number of swaps necessary to make a string balanced.
Note - Strings S1 and S2 can be empty.
Example 1:
Input  : []][][
Output : 2
Explanation :
First swap: Position 3 and 4
[][]][
Second swap: Position 5 and 6
[][][]
Example 2:
Input : [[][]]
Output : 0 
Explanation:
String is already balanced.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function minimumNumberOfSwaps() which takes the string S and return minimum number of operations required to balance the bracket sequence.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1<=|S|<=100000

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Greedy algorithms

Starter code: #User function Template for python3

class Solution:

    def minimumNumberOfSwaps(self,S):

        # code here 

Solutions:
class Solution:

	def minimumNumberOfSwaps(self, s):
		swap = 0
		imbalance = 0
		for i in s:
			if i == '[':
				imbalance -= 1
			else:
				imbalance += 1
				if imbalance > 0:
					swap += imbalance
		return swap


class Solution:

	def minimumNumberOfSwaps(self, s):
		op = 0
		cl = 0
		f = 0
		ans = 0
		for i in range(len(s)):
			if s[i] == ']':
				cl += 1
				f = cl - op
			else:
				op += 1
				if f > 0:
					ans += f
					f -= 1
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		c1 = 0
		res = 0
		for i in S:
			if i == '[':
				c1 += 1
			else:
				c1 -= 1
				if c1 < 0:
					res = res - c1
		return res


class Solution:

	def minimumNumberOfSwaps(self, S):
		cnt = 0
		ans = 0
		n = len(S)
		for i in range(n):
			if S[i] == '[' and cnt >= 0:
				cnt += 1
			elif S[i] == ']':
				cnt -= 1
			if S[i] == '[' and cnt < 0:
				ans += abs(cnt)
				cnt += 1
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		ans = 0
		val = 0
		for i in S:
			if i == '[':
				val += 1
			else:
				val -= 1
				if val < 0:
					ans = ans - val
		return ans


class Solution:

	def minimumNumberOfSwaps(self, string):
		n = len(string)
		if n % 2 != 0:
			return -1
		left = right = swaps = imbalance = 0
		for i in range(n):
			if string[i] == '[':
				left += 1
			else:
				right += 1
				imbalance = right - left
				if imbalance > 0:
					swaps += imbalance
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		open = 0
		close = 0
		swap = 0
		ub = 0
		for i in range(len(S)):
			if S[i] == '[':
				open += 1
				if ub > 0:
					swap += ub
					ub -= 1
			else:
				close += 1
				ub = close - open
		return swap


class Solution:

	def minimumNumberOfSwaps(self, S):
		count = 0
		stack = []
		for i in S:
			if stack:
				if stack[-1] == '[':
					if i == ']':
						stack.pop()
					else:
						stack.append(i)
				elif i == '[':
					count += len(stack)
					stack.pop()
				else:
					stack.append(i)
			else:
				stack.append(i)
		return count


class Solution:

	def minimumNumberOfSwaps(self, S):
		swap = 0
		x = 0
		for i in range(len(S)):
			if S[i] == '[':
				x -= 1
			else:
				x += 1
				if x > 0:
					swap += x
		return swap


class Solution:

	def minimumNumberOfSwaps(self, S):
		ct = 0
		res = 0
		for i in range(len(S)):
			if S[i] == '[':
				ct -= 1
			else:
				ct += 1
				if ct > 0:
					res += ct
		return res


class Solution:

	def minimumNumberOfSwaps(self, S):
		swap = 0
		op = 0
		cl = 0
		unbl = 0
		for i in S:
			if i == '[':
				op += 1
				if unbl > 0:
					swap += unbl
					unbl -= 1
			else:
				cl += 1
				unbl = cl - op
		return swap


class Solution:

	def minimumNumberOfSwaps(self, S):
		opene = 0
		close = 0
		count = 0
		fault = 0
		for i in S:
			if i == ']':
				close += 1
				fault = close - opene
			else:
				opene += 1
				if fault > 0:
					count += fault
					fault -= 1
		return count


class Solution:

	def minimumNumberOfSwaps(self, S):
		open = 0
		close = 0
		swaps = 0
		ub = 0
		for i in S:
			if i == '[':
				open += 1
				if ub > 0:
					swaps += ub
					ub -= 1
			else:
				close += 1
				ub = close - open
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		(opn, close, unbal, swap) = (0, 0, 0, 0)
		for i in S:
			if i == '[':
				opn += 1
				if unbal > 0:
					swap += unbal
					unbal -= 1
			else:
				close += 1
				unbal = close - opn
		return swap


class Solution:

	def minimumNumberOfSwaps(self, S):
		stk = []
		(cnt, res) = (0, 0)
		for x in S:
			if x == '[':
				if cnt < 0:
					res += abs(cnt)
				cnt += 1
			else:
				cnt -= 1
		return res


class Solution:

	def minimumNumberOfSwaps(self, S):
		(op, cs) = (0, 0)
		ub = 0
		swaps = 0
		for ch in S:
			if ch == ']':
				cs += 1
				ub = cs - op
			else:
				op += 1
				if ub > 0:
					swaps += ub
					ub -= 1
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		open = close = fault = ans = 0
		for x in S:
			if x == ']':
				close += 1
				fault = close - open
			else:
				open += 1
				if fault > 0:
					ans += fault
					fault -= 1
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		arr = []
		for i in range(len(S)):
			if S[i] == '[':
				arr.append(i)
		ind = 0
		count = 0
		sums = 0
		S = list(S)
		for i in range(len(S)):
			if S[i] == '[':
				count += 1
				ind += 1
			else:
				count -= 1
			if count < 0:
				sums += arr[ind] - i
				(S[i], S[arr[ind]]) = (S[arr[ind]], S[i])
				ind += 1
				count = 1
		return sums


class Solution:

	def minimumNumberOfSwaps(self, S):
		(op, cl, ub, sw) = (0, 0, 0, 0)
		for i in range(len(S)):
			if S[i] == '[':
				op += 1
				if ub > 0:
					sw += ub
					ub -= 1
			else:
				cl += 1
				ub = cl - op
		return sw


class Solution:

	def minimumNumberOfSwaps(self, S):
		open = 0
		close = 0
		fault = 0
		ans = 0
		for i in range(len(S)):
			if S[i] == ']':
				close += 1
				fault = close - open
			else:
				open += 1
				if fault > 0:
					ans += fault
					fault -= 1
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		opened = 0
		res = 0
		for c in S:
			if c == '[':
				if opened < 0:
					res += abs(opened)
				opened += 1
			else:
				opened -= 1
		return res + opened // 2


class Solution:

	def minimumNumberOfSwaps(self, s):
		pos = []
		for i in range(len(s)):
			if s[i] == '[':
				pos.append(i)
		p = 0
		cnt = 0
		ans = 0
		s = list(s)
		for i in range(len(s)):
			if s[i] == '[':
				p += 1
				cnt += 1
			else:
				cnt -= 1
			if cnt < 0:
				ans += pos[p] - i
				(s[i], s[pos[p]]) = (s[pos[p]], s[i])
				p += 1
				cnt = 1
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		count = 0
		ans = 0
		for i in range(len(S)):
			if S[i] == '[':
				count -= 1
			else:
				count += 1
				if count > 0:
					ans = ans + count
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		openn = 0
		close = 0
		ub = 0
		swaps = 0
		for b in S:
			if b == '[':
				openn += 1
				if ub > 0:
					swaps += ub
					ub -= 1
			else:
				close += 1
			ub = close - openn
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		n = len(S)
		(swap, count_open) = (0, 0)
		for i in S:
			if i == '[':
				count_open += 1
			else:
				count_open -= 1
				if count_open < 0:
					swap -= count_open
		return swap


class Solution:

	def minimumNumberOfSwaps(self, s):
		open_positions = []
		for (i, c) in enumerate(s):
			if c == '[':
				open_positions.append(i)
		(open_count, pos, swaps) = (0, 0, 0)
		s = list(s)
		for (i, c) in enumerate(s):
			if c == '[':
				open_count += 1
				pos += 1
			elif open_count > 0:
				open_count -= 1
			else:
				swaps += open_positions[pos] - i
				(s[i], s[open_positions[pos]]) = (s[open_positions[pos]], s[i])
				pos += 1
				open_count = 1
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		res = 0
		check = 0
		for each in S:
			if each == '[':
				check += 1
			else:
				check -= 1
				if check < 0:
					res += -check
		return res


class Solution:

	def minimumNumberOfSwaps(self, S):
		(ch, ans) = (0, 0)
		for each in S:
			if each == '[':
				ch += 1
			else:
				ch -= 1
				if ch < 0:
					ans += -ch
		return ans


class Solution:

	def minimumNumberOfSwaps(self, input_string):
		open_bracket_count = 0
		close_bracket_count = 0
		answer = 0
		fault = close_bracket_count - open_bracket_count
		n = len(input_string)
		for i in range(0, n):
			element = input_string[i]
			if element == ']':
				close_bracket_count = close_bracket_count + 1
				fault = close_bracket_count - open_bracket_count
			else:
				open_bracket_count = open_bracket_count + 1
				if fault > 0:
					answer = answer + fault
					fault = fault - 1
		return answer


class Solution:

	def minimumNumberOfSwaps(self, S):
		input_string = list(S)
		opening_brackets_index_queue = []
		n = len(input_string)
		for i in range(0, n):
			element = input_string[i]
			if element == '[':
				opening_brackets_index_queue.append(i)
		answer = 0
		count = 0
		for i in range(0, n):
			element = input_string[i]
			if element == '[':
				count = count + 1
				opening_brackets_index_queue.pop(0)
			else:
				count = count - 1
				if count < 0:
					opening_bracket_index = opening_brackets_index_queue.pop(0)
					answer = answer + opening_bracket_index - i
					(input_string[i], input_string[opening_bracket_index]) = (input_string[opening_bracket_index], input_string[i])
					count = 1
		return answer


class Solution:

	def minimumNumberOfSwaps(self, S):
		imbalance = 0
		swaps = 0
		for i in S:
			if i == '[':
				imbalance -= 1
			else:
				imbalance += 1
				if imbalance > 0:
					swaps += imbalance
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		chars = S
		countLeft = 0
		countRight = 0
		swap = 0
		imbalance = 0
		for i in range(len(chars)):
			if chars[i] == '[':
				countLeft += 1
				if imbalance > 0:
					swap += imbalance
					imbalance -= 1
			elif chars[i] == ']':
				countRight += 1
				imbalance = countRight - countLeft
		return swap


class Solution:

	def minimumNumberOfSwaps(self, s):
		pos = []
		for i in range(len(s)):
			if s[i] == '[':
				pos.append(i)
		count = 0
		p = 0
		sum = 0
		s = list(s)
		for i in range(len(s)):
			if s[i] == '[':
				count += 1
				p += 1
			elif s[i] == ']':
				count -= 1
			if count < 0:
				sum += pos[p] - i
				(s[i], s[pos[p]]) = (s[pos[p]], s[i])
				p += 1
				count = 1
		return sum


class Solution:

	def minimumNumberOfSwaps(self, S):
		c = 0
		o = 0
		res = 0
		for i in S:
			if i == ']':
				c = c + 1
			else:
				if c > o:
					res = res + (c - o)
				o = o + 1
		return res


class Solution:

	def minimumNumberOfSwaps(self, s):
		open = 0
		close = 0
		cnt = 0
		for i in s:
			if i == ']':
				close += 1
			else:
				if close > open:
					cnt += close - open
				open += 1
		return cnt


class Solution:

	def minimumNumberOfSwaps(self, S):
		open = 0
		close = 0
		res = 0
		for i in S:
			if i == ']':
				close = close + 1
			else:
				if close > open:
					res = res + (close - open)
				open = open + 1
		return res


class Solution:

	def minimumNumberOfSwaps(self, S):
		swap = 0
		balance = 0
		for i in S:
			if i == '[':
				balance -= 1
			else:
				balance += 1
				if balance > 0:
					swap += balance
		return swap


class Solution:

	def minimumNumberOfSwaps(self, S):
		st = []
		bal = 0
		op = 0
		swap = 0
		for i in range(len(S)):
			if S[i] == '[':
				st.append(i)
		lst = list(S)
		for i in range(len(S)):
			if lst[i] == '[':
				bal += 1
				op += 1
			else:
				bal -= 1
				if bal < 0:
					swap += st[op] - i
					(lst[st[op]], lst[i]) = (lst[i], lst[st[op]])
					bal = 1
					op += 1
		return swap


class Solution:

	def minimumNumberOfSwaps(self, S):
		count = 0
		stack = []
		for item in S:
			if not stack:
				stack.append(item)
			elif stack[-1] == ']' and item == '[':
				count += len(stack)
				stack.pop()
			elif stack[-1] == '[' and item == ']':
				stack.pop()
			else:
				stack.append(item)
		return count


class Solution:

	def minimumNumberOfSwaps(self, S):
		res = 0
		cur = 0
		for i in S:
			if i == '[':
				res += max(cur, 0)
				cur -= 1
			else:
				cur += 1
		return res


class Solution:

	def minimumNumberOfSwaps(self, arr):
		n = len(arr)
		open = close = swap = i = unbalanced = 0
		while open + close != n:
			if arr[i] == '[':
				open += 1
				if unbalanced > 0:
					swap = swap + unbalanced
					unbalanced -= 1
			elif arr[i] == ']':
				close += 1
				unbalanced = close - open
			i += 1
		return swap


class Solution:

	def minimumNumberOfSwaps(self, arr):
		n = len(arr)
		arr = list(arr)
		open = closed = swap = i = 0
		while i < n:
			if arr[i] == '[':
				open += 1
				i += 1
			elif arr[i] == ']':
				if open != 0:
					open -= 1
					i += 1
				else:
					j = i + 1
					while j < n:
						if arr[j] == '[':
							break
						j += 1
					while j != i:
						(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
						j -= 1
						swap += 1
		return swap


class Solution:

	def minimumNumberOfSwaps(self, S):
		n = len(S)
		s = S
		ans = 0
		top = 0
		for i in range(n):
			if s[i] == ']':
				top -= 1
				if top < 0:
					ans += abs(top)
			else:
				top += 1
		return ans


from math import ceil

class Solution:

	def minimumNumberOfSwaps(self, s):
		ans = 0
		count = 0
		for i in s:
			if i == '[':
				count += 1
			else:
				count -= 1
				if count < 0:
					ans += -count
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		openBracesPositions = list()
		for i in range(len(S)):
			if S[i] == '[':
				openBracesPositions.append(i)
		answer = 0
		bracePointer = 0
		openBracePointer = 0
		S = list(S)
		for i in range(len(S)):
			if S[i] == '[':
				bracePointer += 1
				openBracePointer += 1
			else:
				bracePointer -= 1
			if bracePointer < 0:
				answer += openBracesPositions[openBracePointer] - i
				(S[i], S[openBracesPositions[openBracePointer]]) = (S[openBracesPositions[openBracePointer]], S[i])
				bracePointer = 1
				openBracePointer += 1
		return answer


class Solution:

	def minimumNumberOfSwaps(self, S):
		bracket = 0
		swaps = 0
		for i in range(len(S)):
			if S[i] == ']':
				bracket += 1
			if S[i] == '[':
				bracket -= 1
			if bracket > 0 and S[i] == ']':
				swaps += bracket
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		(close, mx) = (0, 0)
		for i in S:
			if i == '[':
				close -= 1
			else:
				close += 1
				if close > 0:
					mx += close
		return mx


def findNextOpen(i, S):
	n = len(S)
	for j in range(i, n):
		if S[j] == '[':
			return j
	return -1

class Solution:

	def minimumNumberOfSwaps(self, S):
		S = [x for x in S]
		n = len(S)
		(open, close) = (0, 0)
		totalCost = 0
		for i in range(n):
			if S[i] == '[':
				open += 1
			else:
				close += 1
			if open < close:
				nextOpen = findNextOpen(i, S)
				S[nextOpen] = ']'
				S[i] = '['
				cost = nextOpen - i
				totalCost += cost
				open += 1
				close -= 1
		return totalCost


import math

class Solution:

	def minimumNumberOfSwaps(self, S):
		ans = c = 0
		for i in range(len(S)):
			if S[i] == ']':
				c -= 1
			else:
				if c < 0:
					ans += abs(c)
				c += 1
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		o = 0
		c = 0
		unb = 0
		swap = 0
		for i in S:
			if i == '[':
				o += 1
				if unb > 0:
					swap += unb
					unb -= 1
			else:
				c += 1
				unb = c - o
		return swap


class Solution:

	def minimumNumberOfSwaps(self, s):
		s = list(s)
		n = len(s)
		ob = []
		for (i, c) in enumerate(s):
			if c == '[':
				ob.append(i)
		p = swaps = count = 0
		for (i, c) in enumerate(s):
			if c == '[':
				p += 1
				count += 1
			else:
				count -= 1
				if count < 0:
					count = 1
					(s[i], s[ob[p]]) = (s[ob[p]], s[i])
					swaps += ob[p] - i
					p += 1
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		swap = 0
		left = 0
		right = 0
		for i in range(len(S)):
			if S[i] == '[':
				if right > 0:
					swap += right
					right -= 1
				else:
					left += 1
			elif left <= 0:
				right += 1
			else:
				left -= 1
		return swap


class Solution:

	def minimumNumberOfSwaps(self, S):
		n = len(S)
		ans = 0
		op = 0
		cd = 0
		seen = 0
		i = 0
		while i < n:
			if S[i] == '[':
				op += 1
				if cd > 0:
					if cd == 1:
						op -= 1
						ans += 1
						cd -= 1
					else:
						op -= 1
						ans += cd
						cd -= 1
				elif i + 1 < n and S[i + 1] == ']':
					op -= 1
					i += 1
			elif op > 0:
				op -= 1
			else:
				cd += 1
			i += 1
		return ans


class Solution:

	def minimumNumberOfSwaps(self, S):
		c = 0
		m = 0
		for i in S:
			if i == '[':
				c = c + 1
			else:
				c = c - 1
				if c < 0:
					m = m - c
		return m


class Solution:

	def minimumNumberOfSwaps(self, S):
		opening_pos = []
		S = list(S)
		for i in range(len(S)):
			if S[i] == '[':
				opening_pos.append(i)
		balance = 0
		swaps = 0
		p = 0
		for i in range(len(S)):
			if S[i] == '[':
				balance += 1
				p += 1
			else:
				balance -= 1
				if balance < 0:
					next_opening_idx = opening_pos[p]
					swaps += next_opening_idx - i
					p += 1
					(S[i], S[next_opening_idx]) = (S[next_opening_idx], S[i])
					balance = 1
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		closebrackets = 0
		openbrackets = 0
		ans = 0
		for i in S:
			if i == ']':
				closebrackets += 1
			else:
				if closebrackets > openbrackets:
					ans += closebrackets - openbrackets
				openbrackets += 1
		return ans


from collections import deque

class Solution:

	def minimumNumberOfSwaps(self, S):
		swaps = 0
		deq = deque()
		l = len(S)
		i = 0
		while i < l:
			if not deq:
				deq.append(S[i])
			elif deq[0] == '[':
				if S[i] == ']':
					deq.pop()
				else:
					deq.append('[')
			elif S[i] == '[':
				swaps += len(deq)
				deq.popleft()
			else:
				deq.append(']')
			i += 1
		return swaps


class Solution:

	def minimumNumberOfSwaps(self, S):
		swap = 0
		imbalanced = 0
		cntl = 0
		cntr = 0
		for i in S:
			if i == '[':
				cntl += 1
				if imbalanced > 0:
					swap += imbalanced
					imbalanced -= 1
			elif i == ']':
				cntr += 1
				imbalanced = cntr - cntl
		return swap


class Solution:

	def minimumNumberOfSwaps(self, a):
		ans = 0
		imbalance = 0
		for i in a:
			if i == '[':
				imbalance -= 1
			else:
				imbalance += 1
				if imbalance > 0:
					ans += imbalance
		return ans