Problem title
Difficulty
Avg time to solve

Unique Binary Search Trees
Moderate
20 mins
Number Of Good Leaf Nodes Pairs
Easy
15 mins
BALLOONS GAME
Easy
10 mins
Lowest Common Ancestor of a Binary Tree III
Moderate
25 mins
Sort String with alternate lower upper.
Easy
15 mins
Sort Elements By Frequency
Easy
15 mins
Binary Tree Maximum Path Sum
Moderate
20 mins
Construct Quad Tree
Moderate
30 mins
Collect Leaves
Moderate
20 mins
Redundant Connection - I
Moderate
15 mins
3

Remove Invalid Parentheses

Difficulty: HARD
Contributed By
Avg. time to solve
50 min
Success Rate
50%

Problem Statement

You are given a string consisting only of parentheses and letters. Your task is to remove the minimum number of invalid parentheses and return all possible unique, valid strings thus obtained.

Note:

1) A string is valid only if every left parenthesis has corresponding right parentheses in the same order.

For example Given ‘STR’ = (())()) is not a valid string, whereas ‘STR’ = (())() is a valid string.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first and the only line of each test case contains a single string ‘STR’ representing the parenthesis.

Output Format:

For each test case, return all possible unique, valid strings after removing the minimum number of parentheses. 

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= |STR| <= 50

Time Limit: 1 second

Sample Input 1:

2
(((a))()
)(()))

Sample Output 1:

(((a))) ((a))()
(())

Explanation of Sample Output 1:

Test Case 1 :  
Given ‘STR’ = (((a))()
From this string, two valid strings can be generated after removing only one parenthesis, which is minimum.
One way is to remove the parenthesis at index 6 to generate (((a))).
Another way is to remove either the first, second, or third parenthesis, which will result in the same string, i.e., ((a))().

Test Case 2 : 
Given ‘STR’ = )(()))
The minimum number of invalid parentheses required to be removed is 2. We have to remove the first and last parentheses to generate a valid string.
So the valid string is (()).

Sample Input 2:

1
(()(()(())

Sample Output 2:

()()(()) ()(()()) (())(()) (()()()) (()(()))
Reset Code
Full screen
copy-code
Console