Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X

Remove Invalid Parentheses

Average time to solve is 50m
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.


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:


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:


Sample Output 2:

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