# Remove Invalid Parentheses

Hard
0/120
Average time to solve is 50m

## 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.
``````
Detailed explanation ( Input/output format, Notes, Images )

#### 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:

``````()()(()) ()(()()) (())(()) (()()()) (()(()))
``````
Console