Table of Contents
Problem Statement
The Minimum Remove to Make Valid Parentheses LeetCode Solution – You are given a string s of ‘(‘, ‘)’ and lowercase English characters.
Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and returns any valid string.
Formally, a parentheses string is valid if and only if:
- It is the empty string, that contains only lowercase characters, or
- It can be written as AB (A concatenated with B), where A and B are valid strings, or
- It can be written as (A), where A is a valid string.
Example:
s = "lee(t(c)o)de)"
"lee(t(c)o)de"
Explanation:
We can remove the last closing parentheses to make the string s valid.
s = "))(("""
Explanation:
An empty string is also valid.
Approach:
We will maintain a variable called “count”. We will increase it if we come across an opening bracket and decrease it when we encounter a closing bracket. Whenever the value of “count” goes negative means then we cannot take that closing bracket, so we will remove it.
After that, we will remove the “count” number of opening brackets from the end as there are no closing brackets to match them.
Code
Minimum Remove to make Valid Parentheses C++ Solution:
#include <bits/stdc++.h>
using namespace std;
string minRemoveToMakeValid(string s)
{
string temp;
int cnt = 0;
for (auto ele : s)
{
if (ele == '(')
{
cnt++;
}
else if (ele == ')')
{
cnt--;
}
if (cnt < 0)
{
cnt++;
}
else
{
temp += ele;
}
}
string answer;
int n = temp.length();
for (int i = n - 1; i >= 0; i--)
{
if (temp[i] != '(' or cnt <= 0)
{
answer += temp[i];
}
else
{
cnt--;
}
}
reverse(answer.begin(), answer.end());
return answer;
}
int main()
{
string s = "lee(t(c)o)de)";
cout << minRemoveToMakeValid(s) << endl;
return 0;
}"lee(t(c)o)de"
Minimum Remove to make Valid Parentheses Java Solution:
public class TutorialCup {
public static String minRemoveToMakeValid(String s) {
int n = s.length();
StringBuilder temp = new StringBuilder();
int count = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') {
count++;
} else if (s.charAt(i) == ')') {
count--;
}
if (count < 0) {
count++;
} else {
temp.append(s.charAt(i));
}
}
n = temp.length();
StringBuilder answer = new StringBuilder();
for (int i = n - 1; i >= 0; i--) {
if (temp.charAt(i) != '(' || count <= 0) {
answer.append(temp.charAt(i));
} else {
count--;
}
}
answer.reverse();
return answer.toString();
}
public static void main(String[] args) {
String s = "lee(t(c)o)de)";
System.out.println(minRemoveToMakeValid(s));
}
}"lee(t(c)o)de"
Complexity Analysis for Minimum Remove to Make Valid Parentheses LeetCode Solution:
Time Complexity
The time complexity of the above code is O(n) because we are traversing the string only twice, where n is the length of the input string.
Space Complexity
The space complexity of the above code is O(n) because we are using creating a new string.