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.
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.
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.
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 5
1 <= |STR| <= 50
Time Limit: 1 second
Sample Input 1:
Sample Output 1:
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:
Sample Output 2:
()()(()) ()(()()) (())(()) (()()()) (()(()))