Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Remove Invalid Parentheses

Hard
0/120
Average time to solve is 50m
11 upvotes
Asked in companies
UberPaypalMAQ Software

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:

()()(()) ()(()()) (())(()) (()()()) (()(()))
Full screen
Console