Given a string S of opening and closing brackets '(' and ')' only. The task is to find an equal point. An equal point is an index such that the number of closing brackets on right from that point must be equal to number of opening brackets before that point.
Example 1:
Input: str = "(())))("
Output: 4
Explanation:
After index 4, string splits into (())
and ))(. Number of opening brackets in the
first part is equal to number of closing
brackets in the second part.
Example 2:
Input : str = "))"
Output: 2
Explanation:
As after 2nd position i.e. )) and "empty"
string will be split into these two parts:
So, in this number of opening brackets i.e.
0 in the first part is equal to number of
closing brackets in the second part i.e.
also 0.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function findIndex() which takes the string S as inputs and returns the occurrence of the equal point in the string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ S ≤ 10^{6}
String can be unbalanced

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def findIndex(self,str):

        # Your code goes here 



Solutions:
class Solution:

	def findIndex(self, str):
		if str == ')':
			return 1
		if str == '(':
			return 0
		open_brackets = 0
		close_brackets = str.count(')')
		for i in range(len(str)):
			if str[i] == '(':
				open_brackets += 1
			elif str[i] == ')':
				close_brackets -= 1
			if open_brackets == close_brackets:
				return i + 1
		return len(str)


class Solution:

	def findIndex(self, str):
		count = 0
		n = len(str)
		for i in range(n):
			if str[i] == ')':
				count += 1
		for i in range(n):
			if count == i:
				return i
		return n


class Solution:

	def findIndex(self, str):
		l = len(str)
		opn = [0] * (l + 1)
		close = [0] * (l + 1)
		index = -1
		opn[0] = 0
		close[l] = 0
		if str[0] == '(':
			opn[1] = 1
		if str[l - 1] == ')':
			close[l - 1] = 1
		for i in range(1, l):
			if str[i] == '(':
				opn[i + 1] = opn[i] + 1
			else:
				opn[i + 1] = opn[i]
		for i in range(l - 2, -1, -1):
			if str[i] == ')':
				close[i] = close[i + 1] + 1
			else:
				close[i] = close[i + 1]
		if opn[l] == 0:
			return l
		if close[0] == 0:
			return 0
		for i in range(l + 1):
			if opn[i] == close[i]:
				index = i
		return index


class Solution:

	def findIndex(self, s):
		n = len(s)
		for i in s:
			if i == '(':
				n -= 1
		return n


class Solution:

	def findIndex(self, str):
		close = str.count(')')
		open = 0
		for i in range(len(str)):
			if str[i] == '(':
				open += 1
			else:
				close -= 1
			if open == close:
				return i + 1
		return 0


class Solution:

	def findIndex(self, str):
		cnt_close = 0
		l = len(str)
		for i in range(l):
			if str[i] == ')':
				cnt_close = cnt_close + 1
		for i in range(l):
			if cnt_close == i:
				return i
		return l


class Solution:

	def findIndex(self, str):
		i = 0
		j = len(str) - 1
		while i <= j:
			mid = i + (j - i) // 2
			if str[:mid].count('(') == str[mid:].count(')'):
				return mid
			elif str[:mid].count('(') > str[mid:].count(')'):
				j = mid - 1
			else:
				i = mid + 1
		return len(str)


class Solution:

	def findIndex(self, str):
		c = 0
		a = str.count('(')
		if a == len(str):
			return 0
		b = len(str) - a
		for i in range(len(str)):
			if str[i] == '(':
				c += 1
			else:
				b -= 1
			if c == b:
				return i + 1


class Solution:

	def findIndex(self, str):
		count = 0
		for i in str:
			if i == ')':
				count += 1
		return count


class Solution:

	def findIndex(self, str):
		opening = 0
		for br in str:
			if br == '(':
				opening += 1
		closing = 0
		for i in range(len(str) - 1, -1, -1):
			if str[i] == ')':
				closing += 1
			elif str[i] == '(':
				opening -= 1
			if opening == closing:
				return i
		return len(str)


class Solution:

	def findIndex(self, str):
		return str.count(')')


class Solution:

	def findIndex(self, str):
		l = len(str)
		arri = [0] * (l + 1)
		arrj = [0] * (l + 1)
		arri[0] = 0
		arrj[l] = 0
		if str[0] == '(':
			arri[1] = 1
		if str[l - 1] == ')':
			arrj[l - 1] = 1
		for i in range(1, l):
			if str[i] == '(':
				arri[i + 1] = arri[i] + 1
			else:
				arri[i + 1] = arri[i]
		for j in range(l - 2, -1, -1):
			if str[j] == ')':
				arrj[j] = arrj[j + 1] + 1
			else:
				arrj[j] = arrj[j + 1]
		if arri[l] == 0:
			return l
		if arrj[0] == 0:
			return 0
		index = -1
		for i in range(l + 1):
			if arri[i] == arrj[i]:
				index = i
		return index


class Solution:

	def findIndex(self, str):
		close = 0
		for i in range(len(str)):
			if str[i] == ')':
				close += 1
		return close


from collections import defaultdict

class Solution:

	def findIndex(self, str):
		close = 0
		ll = list(str)
		n = len(ll)
		for i in range(n):
			if ll[i] == ')':
				close += 1
		return close


class Solution:

	def findIndex(self, str):
		dict1 = {}
		dict2 = {}
		count = 0
		dict1[0] = 0
		for i in range(len(str)):
			if str[i] == '(':
				count += 1
			dict1[i + 1] = count
		count = 0
		dict2[len(str)] = 0
		for j in range(len(str) - 1, -1, -1):
			if str[j] == ')':
				count += 1
			dict2[j] = count
		for i in range(len(str) + 1):
			if dict1[i] == dict2[i]:
				return i


class Solution:

	def findIndex(self, str):
		l = 0
		r = len(str) - 1
		while l <= r:
			if str[l] != '(':
				l += 1
			elif str[r] != ')':
				r -= 1
			else:
				l += 1
				r -= 1
		return l


class Solution:

	def findIndex(self, str):
		op = []
		cl = [0 for i in range(len(str))]
		su = 0
		s = 0
		for i in str:
			if i == '(':
				su += 1
			op.append(su)
		for i in range(len(str) - 1, -1, -1):
			if str[i] == ')':
				s += 1
			cl[i] = s
		for i in range(len(op) - 1):
			if op[i] == cl[i + 1]:
				return i + 1
		if op[len(str) - 1] == 0:
			return len(op)
		if cl[0] == 0:
			return 0


class Solution:

	def findIndex(self, str):
		do = {0: 0}
		dc = {0: 0}
		i = 1
		for s in str:
			if s == '(':
				do[i] = do[i - 1] + 1
				dc[i] = dc[i - 1]
			elif s == ')':
				dc[i] = dc[i - 1] + 1
				do[i] = do[i - 1]
			i += 1
		n = len(str)
		for i in range(1, n + 1):
			if do[i - 1] == dc[n] - dc[i - 1]:
				return i - 1
		return n


class Solution:

	def findIndex(self, str):
		n = len(str)
		totalOpen = 0
		for c in str:
			if c == '(':
				totalOpen += 1
		totalClose = n - totalOpen
		(leftOpen, rightClose) = (0, totalClose)
		if leftOpen == rightClose:
			return 0
		for (i, c) in enumerate(str):
			if c == '(':
				leftOpen += 1
			else:
				rightClose -= 1
			if leftOpen == rightClose:
				return i + 1


class Solution:

	def findIndex(self, str):
		lsum = 0
		s = 0
		for i in str:
			if i == ')':
				s += 1
		for i in range(len(str)):
			if lsum == s:
				return i
			if i == '(':
				lsum += 1
			else:
				s -= 1
		return i + 1


class Solution:

	def findIndex(self, str):
		a = b = 0
		for i in str:
			if i == '(':
				a += 1
			else:
				b += 1
		c = k = 0
		for i in str:
			if c == b:
				return k
			if i == '(':
				c += 1
			else:
				b -= 1
			if c == b:
				k += 1
				return k
			k += 1


class Solution:

	def findIndex(self, str):
		i = 0
		j = 0
		while i + j < len(str):
			if str[i] == ')':
				i += 1
			elif str[-j - 1] == '(':
				j += 1
			else:
				i += 1
				j += 1
		return i


class Solution:

	def findIndex(self, s):
		n = len(s)
		cnt = 0
		for i in range(len(s)):
			if s[i] == '(':
				cnt += 1
		return abs(cnt - n)


class Solution:

	def findIndex(self, str1):
		count = 0
		for i in range(len(str1)):
			if str1[i] == ')':
				count += 1
		return count


class Solution:

	def findIndex(self, str):
		l = len(str)
		o = [0] * (l + 1)
		c = [0] * (l + 1)
		index = -1
		o[0] = 0
		c[l] = 0
		if str[0] == '(':
			o[1] = 1
		if str[l - 1] == ')':
			c[l - 1] = 1
		for i in range(1, l):
			if str[i] == '(':
				o[i + 1] = o[i] + 1
			else:
				o[i + 1] = o[i]
		for i in range(l - 2, -1, -1):
			if str[i] == ')':
				c[i] = c[i + 1] + 1
			else:
				c[i] = c[i + 1]
		if o[l] == 0:
			return l
		if c[0] == 0:
			return 0
		for i in range(l + 1):
			if o[i] == c[i]:
				index = i
		return index


class Balance(object):

	def __init__(self):
		pass

	def balanced_pos(self, bra_str: str):
		left = 0
		right = len(bra_str) - 1
		while left < right:
			if bra_str[left] == ')':
				left += 1
			elif bra_str[right] == '(':
				right -= 1
			elif bra_str[left] == '(' and bra_str[right] == ')':
				left += 1
				right -= 1
		print('left ', left, 'right ', right)
		if left == 0:
			return -1
		elif right == len(bra_str) - 1:
			return len(bra_str)
		else:
			return right + 1

	def balanced_pos2(self, brstr):
		if len(brstr) == 1:
			if brstr[0] == '(':
				return 0
			else:
				return 1
		opbr = [0] * len(brstr)
		clbr = [0] * len(brstr)
		for i in range(1, len(brstr)):
			if brstr[i - 1] == '(':
				opbr[i] = opbr[i - 1] + 1
			else:
				opbr[i] = opbr[i - 1]
		for j in range(len(brstr) - 1, -1, -1):
			if j == len(brstr) - 1:
				if brstr[j] == ')':
					clbr[j] = 1
			elif brstr[j] == ')':
				clbr[j] = clbr[j + 1] + 1
			else:
				clbr[j] = clbr[j + 1]
		if sum(opbr) == 0:
			return len(brstr)
		elif sum(clbr) == 0:
			return -1
		else:
			for j in range(len(brstr) - 1, -1, -1):
				if opbr[j] == clbr[j]:
					return j

class Solution:

	def findIndex(self, str):
		bal = Balance()
		return bal.balanced_pos2(str)


class Solution:

	def findIndex(self, str):
		pol = []
		gbt = 0
		rt = 0
		for ip in range(0, len(str)):
			m = 0
			if str[ip] == '(':
				m = 1
				gbt += 1
			else:
				rt += 1
			por = [ip, m, gbt, rt]
			pol.append(por)
		ans = 0
		for mdew in pol:
			lf = mdew[2]
			ab = rt
			ab -= mdew[3]
			if lf == ab:
				ans = mdew[0] + 1
				break
		return ans


class Solution:

	def findIndex(self, str):
		countclose = 0
		ans = 0
		for i in range(len(str)):
			if str[i] == ')':
				countclose += 1
		if len(str) == countclose:
			return countclose
		for i in range(len(str)):
			if countclose == i:
				ans = i
		return ans


class Solution:

	def findIndex(self, str):
		closing = 0
		start = 0
		for i in str:
			if i == ')':
				closing += 1
		i = 0
		while i < len(str):
			if closing == start:
				return i
			if str[i] == '(':
				start += 1
			elif str[i] == ')':
				closing -= 1
			i += 1
		if closing == start:
			return i
		return -1


class Solution:

	def findIndex(self, str):
		n = len(str)
		left = 0
		right = 0
		i = 0
		while i < n:
			for i in range(0, n):
				if str[i] == ')':
					right += 1
			i += 1
		for i in range(0, n):
			if str[i] == '(':
				left += 1
			else:
				right -= 1
			if left == right:
				return i + 1
		return 0


class Solution:

	def findIndex(self, s):
		i = 0
		j = len(s) - 1
		start = 0
		end = 0
		while i <= j:
			if s[i] == '(':
				start += 1
			if s[j] == ')':
				end += 1
			i += 1
			j -= 1
			if start < end:
				j += 1
				end -= 1
			elif start > end:
				i -= 1
				start -= 1
		return i


class Solution:

	def findIndex(self, str):
		le = []
		re = []
		count = 0
		a = str
		le.append(0)
		for i in range(len(a)):
			if a[i] == '(':
				count += 1
			le.append(count)
		count = 0
		re.append(0)
		for i in range(len(a) - 1, -1, -1):
			if a[i] == ')':
				count += 1
			re.append(count)
		re = re[::-1]
		for i in range(len(re)):
			if le[i] == re[i]:
				return i


class Solution:

	def findIndex(self, str):
		ob = 0
		cb = 0
		for i in range(len(str)):
			if str[i] == '(':
				ob += 1
			else:
				cb += 1
		obt = 0
		cbt = 0
		for i in range(len(str)):
			if str[i] == '(':
				obt += 1
			else:
				cbt += 1
			if obt == cb - cbt:
				return i + 1
		return 0


class Solution:

	def findIndex(self, s):
		n = len(s)
		open = [0] * n
		close = [0] * n
		if s[0] == '(':
			open[0] = 1
		for i in range(1, n):
			if s[i] == '(':
				open[i] = open[i - 1] + 1
			else:
				open[i] = open[i - 1]
		if s[n - 1] == ')':
			close[n - 1] = 1
		for i in range(n - 2, -1, -1):
			if s[i] == ')':
				close[i] = close[i + 1] + 1
			else:
				close[i] = close[i + 1]
		if open[n - 1] == 0:
			return n
		if close[0] == 0:
			return 0
		index = -1
		for i in range(n - 1):
			if open[i] == close[i + 1]:
				index = i + 1
		return index


class Solution:

	def findIndex(self, str):
		n = len(str)
		(l, r) = (0, n - 1)
		open_count = 0
		close_count = 0
		res = -1
		while l <= r:
			if open_count == close_count:
				if str[l] == '(':
					open_count += 1
				l += 1
			else:
				if str[r] == ')':
					close_count += 1
					res = r
				r -= 1
		if l - 1 == r and open_count == close_count + 1:
			return r
		elif res == -1:
			return n
		return res


class Solution:

	def findIndex(self, str):
		(c, d) = (0, 0)
		for i in range(len(str)):
			if str[i] == ')':
				c += 1
		return c


class Solution:

	def findIndex(self, string):
		d = dict()
		d1 = dict()
		n = len(string)
		count = 0
		d[0] = 0
		for i in range(n):
			if string[i] == '(':
				count += 1
			d[i + 1] = count
		count = 0
		d1[n] = 0
		for i in range(n):
			if string[n - 1 - i] == ')':
				count += 1
			d1[n - 1 - i] = count
		for i in range(n + 1):
			if d[i] == d1[i]:
				return i