Minimum Remove to Make Valid Parentheses

Med

#1166Time: 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.4 companies

Data structures

String Stack

Companies

Netflix Snap Tencent GE Digital

Prompt

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 <= 10⁵
s[i] is either '(' , ')', or lowercase English letter.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1java 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(); } }

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1java 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(); } }

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1java 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(); } }

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  String minRemoveToMakeValid(String s) {4    Deque<Character> stk = new ArrayDeque<>();5    int x = 0;6    for (int i = 0; i < s.length(); ++i) {7      char c = s.charAt(i);8      if (c == ')' && x == 0) {9        continue;10      }11      if (c == '(') {12        ++x;13      } else if (c == ')') {14        --x;15      }16      stk.push(c);17    }18    StringBuilder ans = new StringBuilder();19    x = 0;20    while (!stk.isEmpty()) {21      char c = stk.pop();22      if (c == '(' && x == 0) {23        continue;24      }25      if (c == ')') {26        ++x;27      } else if (c == '(') {28        --x;29      }30      ans.append(c);31    }32    return ans.reverse().toString();33  }34}

1class Solution {2public:3  string minRemoveToMakeValid(string s) {4    string stk;5    int x = 0;6    for (char &c : s) {7      if (c == ')' && x == 0)8        continue;9      if (c == '(')10        ++x;11      else if (c == ')')12        --x;13      stk.push_back(c);14    }15    string ans;16    x = 0;17    while (stk.size()) {18      char c = stk.back();19      stk.pop_back();20      if (c == '(' && x == 0)21        continue;22      if (c == ')')23        ++x;24      else if (c == '(')25        --x;26      ans.push_back(c);27    }28    reverse(ans.begin(), ans.end());29    return ans;30  }31};

1class Solution:2    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])

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  String minRemoveToMakeValid(String s) {4    Deque<Character> stk = new ArrayDeque<>();5    int x = 0;6    for (int i = 0; i < s.length(); ++i) {7      char c = s.charAt(i);8      if (c == ')' && x == 0) {9        continue;10      }11      if (c == '(') {12        ++x;13      } else if (c == ')') {14        --x;15      }16      stk.push(c);17    }18    StringBuilder ans = new StringBuilder();19    x = 0;20    while (!stk.isEmpty()) {21      char c = stk.pop();22      if (c == '(' && x == 0) {23        continue;24      }25      if (c == ')') {26        ++x;27      } else if (c == '(') {28        --x;29      }30      ans.append(c);31    }32    return ans.reverse().toString();33  }34}

1class Solution {2public:3  string minRemoveToMakeValid(string s) {4    string stk;5    int x = 0;6    for (char &c : s) {7      if (c == ')' && x == 0)8        continue;9      if (c == '(')10        ++x;11      else if (c == ')')12        --x;13      stk.push_back(c);14    }15    string ans;16    x = 0;17    while (stk.size()) {18      char c = stk.back();19      stk.pop_back();20      if (c == '(' && x == 0)21        continue;22      if (c == ')')23        ++x;24      else if (c == '(')25        --x;26      ans.push_back(c);27    }28    reverse(ans.begin(), ans.end());29    return ans;30  }31};

1class Solution:2    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])

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.