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

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)"

Constraints:

  • 1 <= s.length <= 10^5

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 "()":
continue
if char == "(":
stack_ind.append(ind)
elif stack_ind == []:
remove_ind.add(ind)
else:
stack_ind.pop()
remove_ind = remove_ind.union(set(stack_ind))
output = ""
for ind, char in enumerate(s):
if ind in remove_ind:
continue
output+=char
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 @ www.linkedin.com/in/annamariya-jt