Minimum Remove to Make Valid Parentheses — Day 23(Python)

Photo by Md Mahdi on Unsplash

Question for today is one of the favorite problems among Facebook interviewers. Let us look into the question.

1249. Minimum Remove to Make Valid Parentheses

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.

Example 4:

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


  • 1 <= s.length <= 10^5
  • s[i] is one of '(' , ')' and lowercase English letters.

Balanced parenthesis string intends to guarantee that the count of opening parenthesis is equal to the count of the closing parenthesis. A starting parenthesis should always have a closing parenthesis. A closing parenthesis should occur after an open parenthesis.

When we traverse through each character in the string, we need to check if the current character is among ‘(‘ or ‘)’. If yes, we need to check if the character is forming a balanced parenthesis. If yes, keep moving forward. If not, keep track of the indexes that results in unbalanced parenthesis.

As an example, let us consider string with just parenthesis.

s = “((()))”
The above string has balanced parenthesis. The count of open parenthesis is equal to the count of closed parenthesis.

s = “)()”
The above string has unbalanced parentheses. The count of open parenthesis is lesser than the count of closed parenthesis. We see that the string started with “)”, without “(“ before the occurrence of the closing bracket. Hence we have an unbalanced parenthesis. To balance this string, we can remove the first character from the string, therefore the resulting string will be s = “()”.

How should we check if the character at the given index results in an unbalanced parenthesis?

We can make use of a stack that holds the opening parenthesis, and whenever we get a closing parenthesis, pop the opening parenthesis from the stack.

What if the closing parenthesis occurs before the opening parenthesis? We can have a set that holds indexes of such characters.

What should we do about characters other than “(“, “)”? Since we need not perform any manipulations on them, ignore those characters.

Once we traverse through all the characters, we get with few indexes in the stack and set. In the output string, all characters except for characters in the stack and set are included.

Let us look into the code snippet.

class MinParenthesisRemover:
def minRemoveToMakeValid(self, s: str) -> str:
remove_ind = set()
stack_ind = []
for ind, char in enumerate(s):
if char not in "()":
if char == "(":
elif stack_ind == []:
remove_ind = remove_ind.union(set(stack_ind))
output = ""
for ind, char in enumerate(s):
if ind in remove_ind:
return output

Complexity analysis

Time Complexity

We are traversing through the entire string to identify valid and invalid characters, hence time complexity is O(N).

Space Complexity

We are using a set that holds indexes of invalid characters. In worst-case scenario, if our input string is “)))))))))))))” , our set would be of size same as length of input string. Hence space complexity is of O(N).

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.




Software Engineer. Find me @

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

SOLID Principles — Simplified with Illustrations

Django on GAE (google app engine)

Abstraction in Java


Debug Web Applications With HTTP Client | TechAffinity

Hash Log — DxSale July Update

Hack the Box: Quick

Django Intro with Go and Flamingo

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Annamariya Tharayil

Annamariya Tharayil

Software Engineer. Find me @

More from Medium

How to Netboot with iPXE Part 2

How to setup your Cloud Server securely

How to create an awesome Github Profile README ?

TIL: Understanding Github fork