Remove Invalid Parentheses

Here is the link of geeksforgeeks.org.

An expression will be given which can contain open and close parentheses and optionally some characters, No other operator will be there in string. We need to remove minimum number of parentheses to make the input string valid. If more than one valid output are possible removing same number of parentheses then print all such output.

Examples:

Input  : str = “()())()” -
Output : ()()() (())()
There are two possible solutions
"()()()" and "(())()"

Input  : str = (v)())()
Output : (v)()()  (v())()

I interviewed two people, both of them use BFS and wrote the algorithm to find the minimum parenthesis to remove algorithm. After two mock interviews, I also wrote a solution based one code study on geeksongeeks.com.

I am still thinking about the solution with better time complexity.

Here is my practice link.