Given a string with brackets ('[' and ']') and the index of an opening bracket. Find the index of the corresponding closing bracket.
Example 1:
Input:
S = "[ABC[23]][89]"
pos = 0
Output: 8
Explanation: [ABC[23]][89]
The closing bracket corresponding to the
opening bracket at index 0 is at index 8.
Ã¢â¬â¹Example 2:
Input: 
S = "ABC[58]"
pos = 3
Output: 6
Explanation: ABC[58]
The closing bracket corresponding to the
opening bracket at index 3 is at index 6.
Your Task:
You don't need to read input or print anything. Your task is to complete the function closing() which takes a string S and a position pos as inputs and returns the index of the closing bracket corresponding to the opening bracket at index pos.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 2*10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def closing (self,s, pos):

        # your code here

Solutions:
class Solution:

	def closing(self, S, pos):
		cont = 0
		for i in range(pos, len(S)):
			if S[i] == '[':
				cont += 1
			if S[i] == ']':
				cont -= 1
			if cont == 0:
				break
		return i


class Solution:

	def closing(self, s, pos):
		st = []
		for i in range(pos, len(s)):
			if s[i] == '[':
				st.append(i)
			elif s[i] == ']':
				st.pop()
				if not st:
					return i
		return -1


class Solution:

	def closing(self, s, pos):
		c = 0
		for i in range(pos, len(s)):
			if s[i] == '[':
				c += 1
			if s[i] == ']':
				c -= 1
			if c == 0:
				return i
				break


class Solution:

	def closing(self, s, pos):
		open_count = 0
		close_count = 0
		diff = 0
		for i in range(pos, len(s)):
			if s[i] == '[':
				diff = diff + 1
			if s[i] == ']' and diff > 0:
				diff = diff - 1
			if s[i] == ']' and diff == 0:
				return i


class Solution:

	def closing(self, s, pos):
		n = len(s)
		openb = 0
		for i in range(pos, n):
			if s[i] == '[':
				openb += 1
			elif s[i] == ']' and openb > 0:
				openb -= 1
			if s[i] == ']' and openb == 0:
				break
		return i


class Solution:

	def closing(self, s, pos):
		count = 0
		for i in range(pos + 1, len(s)):
			if s[i] == '[':
				count += 1
			if s[i] == ']':
				if count == 0:
					return i
				else:
					count -= 1


class Solution:

	def closing(self, s, pos):
		stck = []
		for i in range(len(s)):
			if s[i] == '[':
				stck.append(i)
			if s[i] == ']':
				if stck.pop() == pos:
					return i


class Solution:

	def closing(self, s, pos):
		a = 0
		for i in range(pos, len(s)):
			if s[i] == '[':
				a += 1
			elif s[i] == ']':
				a -= 1
			if a == 0:
				return i


class Solution:

	def closing(self, s, pos):
		for x in range(pos + 1, len(s)):
			if s[x] == ']':
				return x


class Solution:

	def closing(self, s, pos):
		stack = []
		open = ['[']
		closed = [']']
		for i in range(pos, len(s)):
			if s[i] in open:
				stack.append(s[i])
			elif s[i] in closed:
				stack.pop(0)
				if len(stack) == 0:
					return i


class Solution:

	def closing(self, s, pos):
		stck = list()
		n = len(s)
		for i in range(pos, n):
			temp = s[i]
			if temp == '[':
				stck.append(temp)
			if temp == ']':
				stck.pop()
				if len(stck) == 0:
					return i


class Solution:

	def closing(self, s, pos):
		st = []
		for i in range(pos, len(s)):
			if s[i] == '[':
				st.append(s[i])
			elif s[i] == ']':
				if len(st) > 0 and st[len(st) - 1] == '[':
					st.pop()
				if len(st) == 0:
					return i
			else:
				pass


from collections import deque

class Solution:

	def closing(self, s, i):
		d = deque()
		if s[i] != '[':
			return -1
		for k in range(i, len(s)):
			if s[k] == ']':
				d.popleft()
			elif s[k] == '[':
				d.append(s[k])
			if not d:
				return k


class Solution:

	def is_empty(self, lst):
		return len(lst) == 0

	def add(self, lst, val):
		lst.insert(0, val)

	def remove(self, lst):
		return lst.pop()

	def closing(self, s, pos):
		lst = []
		for x in range(pos, len(s)):
			if s[x] == '[':
				self.add(lst, s[x])
			if s[x] == ']':
				if len(lst) == 1:
					return x
				else:
					self.remove(lst)


class Solution:

	def closing(self, s, pos):

		class Stack:

			def __init__(self):
				self.data = []

			def push(self, item):
				self.data.append(item)

			def pop(self):
				if self.data == []:
					return print('STACK is empty')
				return self.data.pop()

			def print(self):
				print(*self.data)

			def isEmpty(self):
				return self.data == []

			def size(self):
				return len(self.data)

			def top(self):
				return self.data[-1]
		a = Stack()
		s = s[pos:]
		for i in range(len(s)):
			if s[i] == '[':
				a.push(s[i])
			elif s[i] == ']':
				a.pop()
				if a.isEmpty() == True:
					return pos + i


class Solution:

	def closing(self, s, pos):
		stack = []
		No_open = 1
		No_close = 0
		pos += 1
		while No_open != No_close:
			if s[pos] == '[':
				No_open += 1
				stack.append(s[pos])
			elif s[pos] == ']':
				No_close += 1
				stack.append(s[pos])
			pos += 1
		return pos - 1


from collections import deque

class Solution:

	def closing(self, s, pos):
		arr = deque()
		for i in range(pos, len(s)):
			if s[i] == ']':
				arr.popleft()
			elif s[i] == '[':
				arr.append(s[pos])
			if not arr:
				return i
		return -1
		for item in s:
			if item == '[':
				matchingbraceindex = s.find(']', item)
			elif item == ']':
				matchingbraceindex = s.rfind('[', 0, item)


class Solution:

	def closing(self, s, pos):
		opcount = 0
		count = 0
		clcount = 0
		stop = s.index(']')
		for x in range(pos + 1, stop):
			if x == '[':
				opcount += 1
		counter = 0
		for y in s[stop:]:
			counter += 1
			if y == ']':
				clcount += 1
			if clcount == opcount + 1:
				break
		return stop + counter - 1


class Solution:

	def closing(self, s, pos):
		left_stack = []
		for c in range(len(s)):
			if s[c] == '[':
				left_stack.append(c)
			elif s[c] == ']':
				if left_stack[-1] == pos:
					return c
				else:
					left_stack.pop()


class Solution:

	def closing(self, s, pos):
		n = len(s)
		c = 0
		i = pos + 1
		while i < n:
			if s[i] == '[':
				c += 1
			elif s[i] == ']' and c == 0:
				break
			elif s[i] == ']' and c != 0:
				c -= 1
			i += 1
		return i


class Stack:

	def __init__(self):
		self.data = []

	def push(self, item):
		self.data.append(item)

	def pop(self):
		if self.data == []:
			return print('STACK is empty')
		return self.data.pop()

	def print(self):
		print(*self.data)

	def isEmpty(self):
		return True if self.data == [] else False

	def size(self):
		return len(self.data)

class Solution:

	def closing(self, s, pos):
		ind = 0
		st = Stack()
		s = s[pos:]
		for i in s:
			if i == '[':
				st.push(i)
			if i == ']':
				st.pop()
				if st.isEmpty():
					return pos + ind
					break
			ind += 1


class Solution:

	def closing(self, s, pos):
		stack = []
		for (idx, val) in enumerate(s):
			if val == '[':
				stack.append(idx)
			elif val == ']':
				tmp_idx = stack.pop()
				if tmp_idx == pos:
					return idx
		return pos


class Solution:

	def closing(self, s, pos):
		k = 1
		for i in range(pos + 1, len(s)):
			if s[i] == '[':
				k += 1
			elif s[i] == ']':
				k -= 1
			else:
				pass
			if k == 0:
				return i


class Solution:

	def closing(self, s, pos):
		opening = []
		closing = []
		for (j, i) in enumerate(s):
			if i == '[':
				opening.append(j)
			if i == ']':
				if opening[-1] == pos:
					return j
				else:
					opening.pop(len(opening) - 1)
		return 0


class Solution:

	def closing(self, s, pos):
		l = []
		for i in range(len(s)):
			if s[i] == '[':
				if i == pos:
					l.append('*')
				else:
					l.append(i)
			elif s[i] == ']':
				if l[-1] == '*':
					return i
				else:
					l.pop()


class Solution:

	def closing(self, s, pos):
		brackCtr = 0
		while pos < len(s):
			if s[pos] == '[':
				brackCtr += 1
			elif s[pos] == ']':
				brackCtr -= 1
				if brackCtr == 0:
					break
			pos += 1
		return pos


class Solution:

	def closing(self, s, pos):
		i = pos
		stack = []
		while i < len(s):
			if s[i] == '[':
				stack.append('[')
			elif s[i] == ']' and len(stack) != 0:
				stack.pop(len(stack) - 1)
				if len(stack) == 0:
					return i
			i += 1


class Solution:

	def closing(self, s, pos):
		n = len(s)
		lst = ['[']
		for i in range(pos + 1, n):
			if s[i] == '[':
				lst.append('[')
			elif s[i] == ']':
				if len(lst) != 0:
					lst.pop()
				if len(lst) == 0:
					return i


class Solution:

	def closing(self, s, pos):
		l = []
		top = -1
		for i in range(pos, len(s)):
			if s[i] == '[':
				l.append('[')
				top += 1
			elif s[i] == ']':
				if l[top] == '[':
					l = l[:top]
					if len(l) == 0:
						return i
					top = len(l) - 1
		return -1


class Solution:

	def closing(self, s, pos):
		c = 1
		for i in range(pos + 1, len(s)):
			if s[i] == ']':
				c -= 1
			elif s[i] == '[':
				c += 1
			if c == 0:
				break
		return i
t = int(input())
for tc in range(t):
	s = input()
	pos = int(input())
	ob = Solution()
	print(ob.closing(s, pos))


class Solution:

	def closing(self, s, pos):
		d = []
		for i in range(len(s)):
			if s[i] == '[':
				if i == pos:
					d.append('[[')
				else:
					d.append('[')
			elif s[i] == ']':
				f = d[-1]
				d.pop(-1)
				if f == '[[':
					return i
t = int(input())
for tc in range(t):
	s = input()
	pos = int(input())
	ob = Solution()
	print(ob.closing(s, pos))


class Solution:

	def closing(self, s, pos):
		lst = []
		for i in range(pos + 1, len(s)):
			if s[i] == '[':
				lst.append(s[i])
			elif s[i] == ']' and lst.count('[') == 0:
				return i
			elif s[i] == ']':
				lst.pop()
t = int(input())
for tc in range(t):
	s = input()
	pos = int(input())
	ob = Solution()
	print(ob.closing(s, pos))


class Solution:

	def closing(self, s, pos):
		(c, o) = ([], [])
		for i in range(pos + 1, len(s)):
			if s[i] == '[':
				o.append(i)
			elif s[i] == ']':
				c.append(i)
		for i in range(len(c)):
			if not o:
				return s.index(']')
			elif c[i] - o[i] < 0:
				return c[i]


class Solution:

	def closing(self, s, pos):
		m = {}
		c = 0
		for i in range(len(s)):
			if s[i] == '[':
				if i == pos:
					d = c
				m[c] = True
				c = c + 1
		a = d - 1
		b = a
		for i in range(pos, len(s)):
			if s[i] == '[':
				a = a + 1
				b = a
			elif s[i] == ']':
				m[b] = False
				if b == d:
					return i
				else:
					while m[b] == False:
						b = b - 1
t = int(input())
for tc in range(t):
	s = input()
	pos = int(input())
	ob = Solution()
	print(ob.closing(s, pos))


class Solution:

	def closing(self, s, pos):
		m = {}
		c = 0
		for i in range(len(s)):
			if s[i] == '[':
				if i == pos:
					d = c
				m[c] = True
				c = c + 1
		a = d - 1
		b = a
		for i in range(pos, len(s)):
			if s[i] == '[':
				a = a + 1
				b = a
			elif s[i] == ']':
				m[b] = False
				if b == d:
					return i
				else:
					while m[b] == False:
						b = b - 1


class Solution:

	def closing(self, s, pos):
		t = 0
		for i in range(pos, len(s)):
			if s[i] == '[':
				t += 1
			if s[i] == ']':
				t -= 1
				if t == 0:
					return i
		return -1


class Solution:

	def closing(self, s, pos):
		return s.index(']')


class Solution:

	def closing(self, s, pos):
		counter = 0
		a = '['
		b = ']'
		for i in range(pos, len(s)):
			if s[i] == a:
				counter += 1
			if s[i] == b:
				counter -= 1
			if counter == 0:
				return i
				break


class Solution:

	def closing(self, s, pos):
		arr = [s[pos]]
		for i in range(pos + 1, len(s)):
			if s[i] == '[':
				arr.append(s[i])
			if len(arr) != 0 and s[i] == ']':
				arr.pop(len(arr) - 1)
				if len(arr) == 0:
					break
		return i


class Solution:

	def closing(self, s, pos):
		k = []
		for i in range(pos, len(s)):
			if s[i] == '[':
				k.append(i)
			elif s[i] == ']' and len(k) == 1:
				return i
			elif s[i] == ']':
				k.pop()


class Solution:

	def closing(self, s, pos):
		if s[pos] != '[' or pos + 1 == len(s):
			return -1
		else:
			stack = []
			c = -1
			for char in s[pos:]:
				c += 1
				if char == '[':
					stack.append(char)
				elif char == ']':
					if stack != [] and len(stack) > 1:
						top = stack.pop()
					else:
						break
			return pos + c


class Solution:

	def closing(self, s, pos):
		stack = [s[pos]]
		for i in range(pos + 1, len(s)):
			if s[i] == '[':
				stack.append(s[i])
			if s[i] == ']':
				k = stack.pop()
				if len(stack) == 0:
					return i


class Solution:

	def closing(self, s, pos):
		count = 0
		s1 = [x for x in s if x is '[' or ']']
		x = len(s)
		for i in range(pos, x):
			if s1[i] == '[':
				count += 1
			if s1[i] == ']':
				count -= 1
				if count == 0:
					return i


class Solution:

	def closing(self, s, pos):

		def getindex(s, i):
			if s[i] != '[':
				return -1
			queue = []
			for k in range(i, len(s)):
				if s[k] == ']':
					queue.pop(0)
				if s[k] == '[':
					queue.append(s[i])
				if not queue:
					return k
			return -1
		return getindex(s, pos)


class Solution:

	def closing(self, s, pos):
		temp = s[pos + 1:]
		ind = pos
		c = 0
		for i in temp:
			ind += 1
			if i == ']' and c == 0:
				return ind
			elif i == '[':
				c += 1
			elif i == ']' and c != 0:
				c -= 1
			else:
				pass


from collections import deque

class Solution:

	def closing(self, s, pos):
		stack = deque([])
		for i in range(len(s)):
			if s[i] == '[':
				stack.append(pos == i)
			if s[i] == ']':
				is_target = stack.pop()
				if is_target:
					return i
		return -1


class Solution:

	def closing(self, s, pos):
		count = 1
		l = list(s)
		for i in range(pos + 1, len(s)):
			if s[i] == ']':
				count -= 1
			elif s[i] == '[':
				count += 1
			if count == 0:
				return i