You are given a string S that contains parentheses and letters. You have to remove the minimum number of invalid parentheses to make the input string valid.
Return all the possible results in the sorted order.
Example 1:
Input: S = "()())()"
Output: ["(())()","()()()"]
Example 2:
Input: S = "(a)())()"
Output: ["(a())()","(a)()()"]
Example 3:
Input: S = ")("
Output: [""]
Your Task:  
You don't need to read input or print anything. Your task is to complete the function removeInvalidParentheses() which takes the string S as an input parameter and returns an array of strings representing all the valid parentheses that we can form by removing the minimum number of characters from the string.
 
Expected Time Complexity: O(2^{|S|})
Expected Auxiliary Space: O(1)
Constraints:
1 <= |S| <= 20
S consists of lowercase English letters and parentheses '(' and ')'

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def removeInvalidParentheses(self, s: str) -> List[str]:

        ans = []

        

        return ans

Solutions:
class Solution(object):

	def __init__(self):
		self.valid_expressions = None
		self.min_removed = None

	def reset(self):
		self.valid_expressions = set()
		self.min_removed = float('inf')

	def remaining(self, string, index, left_count, right_count, expr, rem_count):
		if index == len(string):
			if left_count == right_count:
				if rem_count <= self.min_removed:
					possible_ans = ''.join(expr)
					if rem_count < self.min_removed:
						self.valid_expressions = set()
						self.min_removed = rem_count
					self.valid_expressions.add(possible_ans)
		else:
			current_char = string[index]
			if current_char != '(' and current_char != ')':
				expr.append(current_char)
				self.remaining(string, index + 1, left_count, right_count, expr, rem_count)
				expr.pop()
			else:
				self.remaining(string, index + 1, left_count, right_count, expr, rem_count + 1)
				expr.append(current_char)
				if string[index] == '(':
					self.remaining(string, index + 1, left_count + 1, right_count, expr, rem_count)
				elif right_count < left_count:
					self.remaining(string, index + 1, left_count, right_count + 1, expr, rem_count)
				expr.pop()

	def removeInvalidParentheses(self, s):
		self.reset()
		self.remaining(s, 0, 0, 0, [], 0)
		return list(self.valid_expressions)


from typing import List

class Solution:

	def removeInvalidParentheses(self, s: str) -> List[str]:
		(left, right) = self.get_right_left_remove_count(s)
		results = set()
		self.get_valid_parenthesis(s, left, right, results, set())
		return list(results)

	def get_valid_parenthesis(self, s, left, right, results, cache):
		if left == 0 and right == 0:
			if self.is_valid_parenthesis(s):
				results.add(s)
		for (idx, c) in enumerate(s):
			temp = s[:idx] + s[idx + 1:]
			if temp in cache:
				continue
			cache.add(temp)
			if c == '(' and left > 0:
				self.get_valid_parenthesis(temp, left - 1, right, results, cache)
			elif c == ')' and right > 0:
				self.get_valid_parenthesis(temp, left, right - 1, results, cache)

	def get_right_left_remove_count(self, s):
		(left, right) = (0, 0)
		for c in s:
			if c == '(':
				left += 1
			elif c == ')':
				right += 1
				if left > 0:
					right -= 1
					left -= 1
		return (left, right)

	def is_valid_parenthesis(self, s):
		count = 0
		for c in s:
			if c == '(':
				count += 1
			elif c == ')':
				count -= 1
			if count < 0:
				return False
		return count == 0


from typing import List

class Solution:

	def isValid(self, s: str) -> bool:
		i = 0
		for w in s:
			if w == '(':
				i += 1
			elif w == ')':
				if i == 0:
					return False
				i -= 1
		if i != 0:
			return False
		return True

	def removeInvalidParentheses(self, s: str) -> List[str]:
		ans = []
		if len(s) == 0:
			return []
		visited = [s]
		bfs = [s]
		stop = False
		while len(bfs) > 0:
			s = bfs.pop(0)
			if self.isValid(s):
				if s not in ans:
					ans.append(s)
				stop = True
			if stop:
				continue
			for i in range(len(s)):
				if s[i] not in ['(', ')']:
					continue
				ns = s[:i] + s[i + 1:]
				if ns not in visited:
					bfs.append(ns)
					visited.append(ns)
		ans.sort()
		return ans


class Solution:

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

	def removeInvalidParentheses(self, s: str):
		mini = self.getmin(s)
		vis = set()
		return self.recursion(mini, vis, s)

	def recursion(self, mini, vis, s):
		if mini == 0:
			minnow = self.getmin(s)
			if minnow == 0 and s not in self.res:
				self.res.append(s)
			return self.res
		for i in range(len(s)):
			if s[i] != ')' and s[i] != '(':
				continue
			left = s[0:i]
			right = s[i + 1:]
			if left + right not in vis:
				self.recursion(mini - 1, vis, left + right)
				vis.add(left + right)
		return self.res

	def getmin(self, s):
		stack = []
		for i in range(len(s)):
			if s[i] != '(' and s[i] != ')':
				continue
			if s[i] == '(':
				stack.append(s[i])
			elif not stack and s[i] == ')':
				stack.append(s[i])
			elif stack and s[i] == ')' and (stack[-1] == '('):
				stack.pop()
			elif stack and s[i] == ')' and (stack[-1] == ')'):
				stack.append(s[i])
		return len(stack)


class Solution:

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

	def removeInvalidParentheses(self, s: str):
		mini = self.getMin(s)
		vis = set()
		return self.fun(vis, s, mini)

	def fun(self, vis, s, mini):
		if mini == 0:
			minic = self.getMin(s)
			if minic == 0 and s not in self.ans:
				self.ans.append(s)
			return self.ans
		for i in range(len(s)):
			if s[i] != ')' and s[i] != '(':
				continue
			left = s[0:i]
			right = s[i + 1:]
			if left + right not in vis:
				self.fun(vis, left + right, mini - 1)
				vis.add(left + right)
		return self.ans

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


from typing import List

class Solution:
	M = []
	Max = 0

	def is_valid_string(self, s: str) -> bool:
		stack = []
		for c in s:
			if c == '(':
				stack.append(c)
			elif c == ')':
				if not stack or stack[-1] != '(':
					return False
				stack.pop()
			elif c.isalpha():
				pass
			else:
				return False
		return not stack

	def removeInvalidParentheses(self, s: str) -> List[str]:
		self.M = []
		self.sol(s, 0)
		res = set()
		maxa = max(self.M)[0]
		for i in self.M:
			if i[0] == maxa:
				res.add(i[1])
		return list(res)

	def sol(self, s, i):
		if len(s) < self.Max:
			return
		if self.is_valid_string(s):
			if len(s) >= self.Max:
				self.Max = len(s)
				self.M.append((self.Max, s))
			return
		if i >= len(s):
			return
		if i == len(s) - 1:
			str = s[:i]
		else:
			str = s[:i] + s[i + 1:]
		self.sol(str, i)
		self.sol(s, i + 1)


from typing import List

class Solution:

	def checkDif(self, s):
		n = len(s)
		open = close = 0
		for i in range(n):
			if s[i] == '(':
				open += 1
			elif s[i] == ')' and open:
				open -= 1
			elif s[i] == ')':
				close += 1
		return (open, close)

	def backTrack(self, leftS, rightS, open, close, vis, ans):
		if leftS + rightS in vis:
			return
		vis.add(leftS + rightS)
		if open == close == 0:
			(l, r) = self.checkDif(leftS + rightS)
			if l + r == 0:
				ans.append(leftS + rightS)
			return
		for i in range(len(rightS)):
			if rightS[i] == '(' and open > 0:
				self.backTrack(leftS, rightS[i + 1:], open - 1, close, vis, ans)
			elif rightS[i] == ')' and close > 0:
				self.backTrack(leftS, rightS[i + 1:], open, close - 1, vis, ans)
			leftS += rightS[i]
		return

	def removeInvalidParentheses(self, s: str):
		(left, right) = self.checkDif(s)
		vis = set()
		ans = []
		self.backTrack('', s, left, right, vis, ans)
		return ans


class Solution:

	def removeInvalidParentheses(self, s):
		ans = []

		def solve(s, removals):
			key = s
			if key in memo:
				return
			memo[key] = True
			if removals == 0:
				removals_needed = find_removals(s)
				if removals_needed == 0:
					ans.append(s)
				return
			for i in range(len(s)):
				leftpart = s[0:i]
				rightpart = s[i + 1:]
				join = leftpart + rightpart
				solve(join, removals - 1)

		def find_removals(s):
			st = []
			for i in range(len(s)):
				if s[i] == '(':
					st.append(s[i])
				elif s[i] == ')':
					if len(st) > 0 and st[-1] == '(':
						st.pop()
					else:
						st.append(s[i])
			return len(st)
		memo = {}
		removals = find_removals(s)
		solve(s, removals)
		return ans


class Solution:

	def removeInvalidParentheses(self, s: str):
		ans = []
		string = [c for c in s]
		n = len(string)

		def isValid(s):
			stack = 0
			for c in s:
				if c == '(':
					stack += 1
				elif c == ')':
					if stack > 0:
						stack -= 1
					else:
						return False
			if stack == 0:
				return True
			else:
				return False

		def stringCharPeaker(s):
			for c in s:
				if c is not None:
					yield c

		def backtrack(index, cnt):
			nonlocal string, n, ans
			if cnt == 0:
				if isValid(string):
					ans.append(''.join(stringCharPeaker(string)))
			else:
				for i in range(index, n):
					if string[i] == '(' or string[i] == ')':
						paranthesis = string[i]
						string[i] = None
						backtrack(i + 1, cnt - 1)
						string[i] = paranthesis
		paranthesesCnt = 0
		for c in string:
			if c == '(' or c == ')':
				paranthesesCnt += 1
		try:
			for removeCnt in range(paranthesesCnt + 1):
				ans = []
				backtrack(0, removeCnt)
				if ans:
					return list(set(ans))
		except Exception as err:
			print(err)
		return ans


class Solution:

	def removeInvalidParentheses(self, s: str):
		res = set()
		maxi = -1
		path = []

		def recur(idx, left_count, right_count):
			nonlocal maxi, res
			if idx >= len(s):
				if left_count == right_count:
					if len(path) > maxi:
						maxi = len(path)
						res = set()
						res.add(''.join(path))
					elif len(path) == maxi:
						res.add(''.join(path))
				return
			if s[idx] == '(':
				path.append(s[idx])
				recur(idx + 1, left_count + 1, right_count)
				path.pop()
				recur(idx + 1, left_count, right_count)
			elif s[idx] == ')':
				recur(idx + 1, left_count, right_count)
				if left_count > right_count:
					path.append(s[idx])
					recur(idx + 1, left_count, right_count + 1)
					path.pop()
			else:
				path.append(s[idx])
				recur(idx + 1, left_count, right_count)
				path.pop()
		recur(0, 0, 0)
		res = list(res)
		return res


class Solution:

	def removeInvalidParentheses(self, s):
		ans = []
		rec(s, 0, 0, [], ans)
		return list(set(ans))

def rec(s, i, balance, curr, ans):
	if i == len(s):
		if balance == 0:
			if not ans:
				ans.append(''.join(curr))
			elif len(curr) == len(ans[-1]):
				ans.append(''.join(curr))
			elif len(curr) > len(ans[-1]):
				ans = [''.join(curr)]
		return
	if balance < 0:
		return
	if s[i] not in '()':
		curr.append(s[i])
		rec(s, i + 1, balance, curr, ans)
		curr.pop()
		return
	curr.append(s[i])
	new_balance = balance + (1 if s[i] == '(' else -1)
	rec(s, i + 1, new_balance, curr, ans)
	curr.pop()
	rec(s, i + 1, balance, curr, ans)


from typing import List

class Solution:

	def valid(self, y):
		c = 0
		for i in y:
			if i == '(':
				c += 1
			elif i == ')':
				c -= 1
			if c < 0:
				return False
		return c == 0

	def removeInvalidParentheses(self, s: str) -> List[str]:
		if len(s) == 0:
			return
		vis = set()
		q = [s]
		vis.add(s)
		res = []
		level = False
		while len(q) != 0:
			x = q.pop(0)
			if self.valid(x):
				res.append(x)
				level = True
			if level:
				continue
			for i in range(len(x)):
				if x[i] != '(' and x[i] != ')':
					continue
				temp = x[:i] + x[i + 1:]
				if temp not in vis:
					vis.add(temp)
					q.append(temp)
		return res


class Solution:

	def removeInvalidParentheses(self, s: str):

		def valid(word):
			left = 0
			open = 0
			for i in range(len(word)):
				if word[i] == ')':
					if open == 0:
						return False
					elif open > 0:
						open -= 1
				elif word[i] == '(':
					open += 1
			return open == 0
		flag = False
		final = []
		queue = [s]
		visited = set()
		while queue:
			n = len(queue)
			if flag == True:
				return list(set(final))
			for _ in range(n):
				word = queue.pop(0)
				if word in visited:
					continue
				visited.add(word)
				if valid(word):
					flag = True
					final.append(word)
				if flag == True:
					continue
				for index in range(len(word)):
					queue.append(''.join((word[i] for i in range(len(word)) if i != index)))
		return list(set(final))


class Solution:

	def removeInvalidParentheses(self, s: str):
		ans = []

		def get_count(string):
			stack = []
			for ch in string:
				if ch == '(':
					stack.append(ch)
				elif ch == ')':
					if stack and stack[-1] == '(':
						stack.pop()
					else:
						stack.append(ch)
			return len(stack)
		visited = set()
		result = set()
		n = len(s)

		def solve(s, count):
			if s in visited:
				return
			if count < 0:
				return
			if count == 0:
				if get_count(s) == 0:
					result.add(s)
				return
			visited.add(s)
			for i in range(n):
				left = s[:i]
				right = s[i + 1:]
				solve(left + right, count - 1)
		solve(s, get_count(s))
		ans = list(result)
		ans.sort()
		return ans


from collections import deque

class Solution:

	def removeInvalidParentheses(self, str):
		ans = []
		if len(str) == 0:
			return

		def isParenthesis(c):
			return c == '(' or c == ')'

		def isValidString(str):
			cnt = 0
			for i in range(len(str)):
				if str[i] == '(':
					cnt += 1
				elif str[i] == ')':
					cnt -= 1
				if cnt < 0:
					return False
			return cnt == 0
		visit = set()
		q = deque([])
		temp = 0
		level = 0
		q.append(str)
		visit.add(str)
		while len(q):
			str = q.popleft()
			if isValidString(str):
				ans.append(str)
				level = True
			if level:
				continue
			for i in range(len(str)):
				if not isParenthesis(str[i]):
					continue
				temp = str[0:i] + str[i + 1:]
				if temp not in visit:
					q.append(temp)
					visit.add(temp)
		return ans


class Solution:

	def removeInvalidParentheses(self, s: str):
		self.ans = []
		count = 0
		temp = ''
		self.solve(count, len(s), s, temp)
		self.ans.sort(key=lambda x: len(x), reverse=True)
		if len(self.ans) == 0 or len(self.ans) == 1:
			return self.ans
		maxlength = len(self.ans[0])
		output = []
		l = maxlength
		i = 0
		while l == maxlength:
			output.append(self.ans[i])
			i += 1
			l = len(self.ans[i])
		return list(set(output))

	def solve(self, count, n, s, temp):
		if n == 0:
			if count == 0:
				self.ans.append(temp)
				return
			return
		if s[n - 1] != '(' and s[n - 1] != ')':
			temp = s[n - 1] + temp
			return self.solve(count, n - 1, s, temp)
		else:
			temp1 = temp[:]
			temp1 = s[n - 1] + temp
			tempcount = count
			if s[n - 1] == '(':
				tempcount -= 1
				if tempcount < 0:
					return self.solve(0, n - 1, s, temp)
			else:
				tempcount += 1
			self.solve(tempcount, n - 1, s, temp1)
			self.solve(count, n - 1, s, temp)
			return


class Solution:

	def removeInvalidParentheses(self, s):
		ans = []

		def isParenthesis(c):
			return c == '(' or c == ')'

		def isValidString(str):
			cnt = 0
			for i in range(len(str)):
				if str[i] == '(':
					cnt += 1
				if str[i] == ')':
					cnt -= 1
				if cnt < 0:
					return False
			return cnt == 0
		if len(s) == 0:
			return
		visit = set()
		q = []
		temp = 0
		level = 0
		q.append(s)
		visit.add(s)
		while len(q):
			str = q[0]
			q.pop(0)
			if isValidString(str):
				ans.append(str)
				level = True
			if level:
				continue
			for i in range(len(str)):
				if not isParenthesis(str[i]):
					continue
				temp = str[0:i] + str[i + 1:]
				if temp not in visit:
					q.append(temp)
					visit.add(temp)
		return ans