# Minimum Remove to Make Valid Parentheses
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/minimum-remove-to-make-valid-parentheses
**Data structures:** String, Stack
**Companies:** [Netflix](https://scaleengineer.com/companies/netflix), [Snap](https://scaleengineer.com/companies/snap), [Tencent](https://scaleengineer.com/companies/tencent), [GE Digital](https://scaleengineer.com/companies/ge-digital)
---
## Problem
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 return **any** valid string.

Formally, a _parentheses string_ is valid if and only if:

* It is the empty string, 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 1:**

**Input:** s = "lee(t(c)o)de)"
**Output:** "lee(t(c)o)de"
**Explanation:** "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

**Example 2:**

**Input:** s = "a)b(c)d"
**Output:** "ab(c)d"

**Example 3:**

**Input:** s = "))(("
**Output:** ""
**Explanation:** An empty string is also valid.

**Constraints:**

* `1 <= s.length <= 105`
* `s[i]` is either `'('` , `')'`, or lowercase English letter.

# Approaches
## Stack and Set of Indices to Remove
This approach involves two main steps. First, we identify all the parentheses that make the string invalid. Second, we construct a new string that excludes these invalid parentheses. We use a stack to track open parentheses and a set to store the indices of parentheses that need to be removed.
**Time:** O(N), where N is the length of the string. We perform two full traversals of the string. Operations on the stack and hash set (push, pop, add, contains) take O(1) time on average. · **Space:** O(N), where N is the length of the string. In the worst-case scenario, such as a string like `((((...` or `))))...`, the stack or the set of indices to remove can grow to a size of N. The `StringBuilder` for the result also requires O(N) space.
**Pros:** The logic is straightforward and easy to reason about.; It correctly identifies all parentheses to be removed in a systematic way.
**Cons:** Uses two auxiliary data structures (a stack and a hash set), leading to higher space overhead compared to other approaches.; Requires two passes over the data: one to find indices and another to build the string.
### Explanation
This approach uses a `Stack` to keep track of the indices of open parentheses `(`. When a closing parenthesis `)` is encountered, we check if the stack is empty. If it is, the `)` is unbalanced and its index is marked for removal. If the stack is not empty, we have found a valid pair, so we pop from the stack. After this first pass, any indices left in the stack correspond to open parentheses that were never closed. These are also unbalanced, so their indices are also marked for removal. We use a `HashSet` to efficiently store and check the indices that need to be removed. Finally, we construct the result by iterating through the original string one more time and appending only the characters whose indices are not in our removal set. ```java class Solution { public String minRemoveToMakeValid(String s) { Set<Integer> indicesToRemove = new HashSet<>(); Stack<Integer> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); } else if (s.charAt(i) == ')') { if (stack.isEmpty()) { indicesToRemove.add(i); } else { stack.pop(); } } } while (!stack.isEmpty()) { indicesToRemove.add(stack.pop()); } StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (!indicesToRemove.contains(i)) { sb.append(s.charAt(i)); } } return sb.toString(); } } ```
### Algorithm
- Initialize an empty stack to store indices of `(` characters. - Initialize an empty `HashSet` called `indicesToRemove` to store indices of parentheses to be removed. - Iterate through the input string `s` from left to right. - If the character is `(`, push its index onto the stack. - If the character is `)`, check the stack. If the stack is empty, it means this `)` has no matching `(`. It's invalid, so add its index to `indicesToRemove`. If the stack is not empty, it means we found a matching pair, so pop from the stack. - After the loop, any indices remaining in the stack correspond to `(` that were never closed. They are also invalid. Pop all remaining indices from the stack and add them to `indicesToRemove`. - Finally, build the result string. Initialize an empty `StringBuilder`. Iterate through the original string `s` again. If the current index is *not* in `indicesToRemove`, append the character to the `StringBuilder`. - Return the `StringBuilder`'s content as a string.

## Two-Pass String Building
This approach avoids using an explicit stack and a set of indices. Instead, it performs two passes over the string to filter out invalid parentheses. The first pass removes invalid closing parentheses, and the second pass removes excess opening parentheses.
**Time:** O(N). The first pass is O(N), the second pass is O(N), and reversing the final result is also O(N). · **Space:** O(N). We use two `StringBuilder` objects. The intermediate builder can grow up to size N, and the final result builder can also grow up to size N.
**Pros:** More space-efficient in practice than the stack/set approach as it avoids the overhead of a HashSet.; The logic is still fairly intuitive, breaking the problem into two distinct steps.
**Cons:** Requires creating two `StringBuilder` objects, one for the intermediate result and one for the final result.; Still requires two full passes over the string data.
### Explanation
In the first pass, we iterate from left to right, building an intermediate string. We use a counter to track open parentheses. We only append a closing parenthesis `)` if there is a corresponding open parenthesis available (i.e., the counter is greater than zero). This effectively removes all misplaced `)`. After this pass, the string is free of invalid `)`, but may have a surplus of `(`. The final value of our counter tells us exactly how many surplus `(` exist. In the second pass, we iterate through our intermediate string from right to left. We remove the required number of `(` from the end of the string to balance the parentheses. The final result is built in reverse and needs to be reversed one last time. ```java class Solution { public String minRemoveToMakeValid(String s) { StringBuilder sb = new StringBuilder(); int openCount = 0; for (char c : s.toCharArray()) { if (c == '(') { openCount++; } else if (c == ')') { if (openCount == 0) continue; openCount--; } sb.append(c); } StringBuilder result = new StringBuilder(); for (int i = sb.length() - 1; i >= 0; i--) { if (sb.charAt(i) == '(' && openCount > 0) { openCount--; continue; } result.append(sb.charAt(i)); } return result.reverse().toString(); } } ```
### Algorithm
- **First Pass (Left to Right):** Remove invalid `)`. - Initialize an empty `StringBuilder` (`sb`) and a counter `openCount = 0`. - Iterate through the input string `s`. - If the character is `(`, increment `openCount` and append it to `sb`. - If the character is a lowercase letter, append it to `sb`. - If the character is `)`, and `openCount > 0`, it means there's a matching `(`. Decrement `openCount` and append the `)` to `sb`. - If the character is `)` and `openCount` is 0, it's an invalid closing parenthesis, so we ignore it. - **Second Pass (Right to Left):** Remove excess `(`. - Initialize a new empty `StringBuilder` (`result`). - Iterate through the intermediate string `sb` from right to left. - If the character is `(` and `openCount > 0` (where `openCount` is the final count from the first pass), this is an excess opening parenthesis. Skip it and decrement `openCount`. - Otherwise, append the character to `result`. - Since `result` was built backwards, reverse it and return as a string.

## In-Place Modification with Placeholder
This is a highly optimized approach that modifies a `StringBuilder` representation of the string in-place over two passes. It uses a placeholder character to mark parentheses for deletion. This avoids creating a separate `StringBuilder` for an intermediate result, thus saving space and improving practical performance.
**Time:** O(N). The algorithm consists of three linear passes over the string's length. · **Space:** O(N). O(N) space is required to create the initial `StringBuilder` from the input string and another O(N) for the final result `StringBuilder`. It avoids creating an additional intermediate data structure.
**Pros:** Most space-efficient of the O(N) space solutions in practice.; Modifies the string representation in-place, which is an elegant and performant technique.
**Cons:** The logic involves mutation and placeholders, which can be slightly less direct to understand than building a new string from scratch.; Technically involves three passes (mark `)`, mark `(`, build result), though all are linear.
### Explanation
This approach first converts the string to a `StringBuilder` to allow in-place modifications. The first pass from left to right uses a counter to find and mark invalid closing parentheses `)` with a placeholder. The second pass goes from right to left to mark the surplus open parentheses `(` with the same placeholder. The number of surplus `(` is known from the final state of the counter after the first pass. Finally, a new string is built by iterating through the modified `StringBuilder` and excluding all placeholder characters. This method is efficient because it reuses the buffer of the first `StringBuilder` instead of creating a new one for the second pass. ```java class Solution { public String minRemoveToMakeValid(String s) { StringBuilder sb = new StringBuilder(s); int openCount = 0; for (int i = 0; i < sb.length(); i++) { if (sb.charAt(i) == '(') { openCount++; } else if (sb.charAt(i) == ')') { if (openCount > 0) { openCount--; } else { sb.setCharAt(i, '#'); } } } for (int i = sb.length() - 1; i >= 0; i--) { if (openCount > 0 && sb.charAt(i) == '(') { sb.setCharAt(i, '#'); openCount--; } } StringBuilder result = new StringBuilder(); for (int i = 0; i < sb.length(); i++) { if (sb.charAt(i) != '#') { result.append(sb.charAt(i)); } } return result.toString(); } } ```
### Algorithm
- Convert the input string `s` into a `StringBuilder` to allow for modification. - **First Pass (Left to Right):** Identify and mark invalid `)`. - Initialize `openCount = 0`. - Iterate through the `StringBuilder`. If `(` is found, increment `openCount`. If `)` is found, decrement `openCount` if it's greater than 0; otherwise, mark the `)` for deletion by replacing it with a placeholder character (e.g., `#`). - **Second Pass (Right to Left):** Identify and mark excess `(`. - After the first pass, `openCount` holds the number of excess open parentheses. - Iterate through the `StringBuilder` from right to left. If `openCount > 0` and the character is `(`, mark it for deletion (replace with `#`) and decrement `openCount`. - **Build Final String:** - Create a new `StringBuilder`. - Iterate through the modified `StringBuilder` and append any character that is not the placeholder `#`. - Return the result as a string.

# Solutions
### Java

```java
class Solution {
public
  String minRemoveToMakeValid(String s) {
    Deque<Character> stk = new ArrayDeque<>();
    int x = 0;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (c == ')' && x == 0) {
        continue;
      }
      if (c == '(') {
        ++x;
      } else if (c == ')') {
        --x;
      }
      stk.push(c);
    }
    StringBuilder ans = new StringBuilder();
    x = 0;
    while (!stk.isEmpty()) {
      char c = stk.pop();
      if (c == '(' && x == 0) {
        continue;
      }
      if (c == ')') {
        ++x;
      } else if (c == '(') {
        --x;
      }
      ans.append(c);
    }
    return ans.reverse().toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string minRemoveToMakeValid(string s) {
    string stk;
    int x = 0;
    for (char &c : s) {
      if (c == ')' && x == 0)
        continue;
      if (c == '(')
        ++x;
      else if (c == ')')
        --x;
      stk.push_back(c);
    }
    string ans;
    x = 0;
    while (stk.size()) {
      char c = stk.back();
      stk.pop_back();
      if (c == '(' && x == 0)
        continue;
      if (c == ')')
        ++x;
      else if (c == '(')
        --x;
      ans.push_back(c);
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minRemoveToMakeValid(self, s: str) -> str: stk = [] x = 0 for c in s: if c == ')' and x == 0: continue if c == '(': x += 1 elif c == ')': x -= 1 stk . append(c) x = 0 ans = [] for c in stk[:: - 1]: if c == '(' and x == 0: continue if c == ')': x += 1 elif c == '(': x -= 1 ans . append(c) return '' . join(ans[:: - 1])

```