Table of Contents
Problem Statement
The Remove Invalid Parentheses Leetcode Solution – states that you’re given a string s that contains parenthesis and lowercase letters. We need to remove the minimum number of invalid parentheses to make the input string valid.
We need to return all possible results in any order.
A string is said to be valid if every closing bracket has an opening bracket and vice versa.
Max Length of string = 25.
There will be at most 20 parentheses in string s.
Example:
Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]
Explanation:
- Given input string is invalid, we need to remove some parentheses to make the input string valid.
- If we remove one parenthesis, then we have a valid string.
- Remove 3rd character from the input string, to get “(a())()”.
- Remove the 6th character from the input string, to get “(a)()()”.
- Hence, a minimum number of parentheses to remove to make the input string valid is 1.
- The above diagram shows the recursion tree where we have skipped the 3rd and 6th characters.
Input: s = ")("Output: [""]
Explanation:
- Given input string is invalid, we need to remove some parentheses to make the input string valid.
- We can remove two parentheses to make the input string valid.
- Remove 1st as well as 2nd parentheses to make the empty string, which is valid.
Approach
Idea:
- The main idea to solve this problem is to use Backtracking.
- The simple solution is to consider 2 options for every parenthesis, either to include it or exclude it and check out the string formed at the end is a valid string or not?. This approach works but gives Time Limit Exceeded verdict here.
- Now, we need to use optimized backtracking to solve this problem efficiently.
- Find the count of all those open parentheses (named as left in the code) which doesn’t have any close parentheses.
- Find count of all those close parentheses (named as right in the code) which doesn’t have any open parentheses.
- The Sum of the above counts is the minimum number of parentheses we need to remove.
- Perform backtracking over left as well as right.
- Whenever we have an open parenthesis, we have two options:
- Take this parenthesis(new_left = left)
- Don’t take this parenthesis, this case occurs when the left is positive (new_left = left-1)
- Whenever we have a close parenthesis, we have two options:
- Take this parenthesis(new_right = right)
- Don’t take this parenthesis, this case occurs when right is positive(new_right = right-1)
- Whenever we have a letter, we have only one option, take this letter and move on.
- Also, for the termination case:
- When we’re done with the input string, check if left==0 and right==0 and pair==0, then take the current string otherwise discard it. pair = number of balanced brackets (check code for better understanding)
- When left + right > len(input string) – index (index = current position that we’re working), no need to move further, since the number of characters to be deleted is strictly more than the number of characters present which is an impossible case.
Code
Remove Invalid Parentheses Leetcode C++ Solution:
class Solution {
public:
unordered_set<string> ans;
void recurse(int index,string s,string curr,int left,int right,int pair){
if(index==s.length()){
if(left==0 and right==0 and pair==0){
ans.insert(curr);
}
return;
}
if(left+right>s.length()-index){
return;
}
if(s[index]!='(' and s[index]!=')'){
recurse(index+1,s,curr+s[index],left,right,pair);
}
else if(s[index]=='('){
recurse(index+1,s,curr+s[index],left,right,pair+1);
if(left){
recurse(index+1,s,curr,left-1,right,pair);
}
}
else{
if(pair>0){
recurse(index+1,s,curr+s[index],left,right,pair-1);
}
if(right){
recurse(index+1,s,curr,left,right-1,pair);
}
}
}
vector<string> removeInvalidParentheses(string s) {
int left = 0,right = 0;
for(auto& c:s){
if(c=='('){
left++;
}
else if(c==')'){
if(left){
left--;
}
else{
right++;
}
}
}
recurse(0,s,"",left,right,0);
return vector<string>(ans.begin(),ans.end());
}
};Remove Invalid Parentheses Leetcode Java Solution:
class Solution {
public List<String> removeInvalidParentheses(String s) {
int left = 0, right = 0,n = s.length();
for(int i=0;i<n;i++){
if(s.charAt(i)=='('){
left++;
}
else if(s.charAt(i)==')'){
if(left>0){
left--;
}
else{
right++;
}
}
}
Set<String> res = new HashSet<>();
dfs(s, 0, res, new StringBuilder(), left, right, 0);
return new ArrayList<String>(res);
}
public void dfs(String s, int i, Set<String> res, StringBuilder sb, int left, int right, int pair) {
if(i==s.length()){
if(left==0 && right==0 && pair==0){
res.add(sb.toString());
}
return;
}
if(left+right>(int)s.length()-i){
return;
}
int len = sb.length();
if(s.charAt(i)=='('){
if(left>0){
dfs(s,i+1,res,sb,left-1,right,pair);
}
dfs(s,i+1,res,sb.append(s.charAt(i)),left,right,pair+1);
}
else if(s.charAt(i)==')'){
if(right>0){
dfs(s,i+1,res,sb,left,right-1,pair);
}
if(pair>0){
dfs(s,i+1,res,sb.append(s.charAt(i)),left,right,pair-1);
}
}
else{
dfs(s,i+1,res,sb.append(s.charAt(i)),left,right,pair);
}
sb.setLength(len);
}
}Complexity Analysis for Remove Invalid Parentheses Leetcode Solution
Time Complexity
The time complexity of the above code is O(2^N) since we have 2 options for every parenthesis and we have explored every option. Hence O(2^N).
Space Complexity
The space complexity of the above code is O(N) since the maximum depth of the recursion goes to N. Note that we aren’t considering the space to store the answer.
Reference: https://en.wikipedia.org/wiki/Parenthesis_(disambiguation)