# Minimum Remove to Make Valid Parentheses LeetCode Solution

Difficulty Level Medium
Stack StringViews 1013

## Problem Statement

The Minimum Remove to Make Valid Parentheses LeetCode SolutionYou 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;
}
}
int n = temp.length();
for (int i = n - 1; i >= 0; i--)
{
if (temp[i] != '(' or cnt <= 0)
{
}
else
{
cnt--;
}
}
}
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();
for (int i = n - 1; i >= 0; i--) {
if (temp.charAt(i) != '(' || count <= 0) {
} else {
count--;
}
}
}

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.

Translate »