Minimum Remove to Make Valid Parentheses
Statement
Given a string s, that may have matched and unmatched parentheses, remove the minimum number of parentheses so that the result string has only matched parentheses.
Constraints
- 1 ≤
s.length()≤ 10³ s[i]is either an opening parenthesis, a closing parenthesis, or a lowercase English character
Solution
"""
production algorithm
"""
class Solution:
def min_remove_parentheses(self, s):
"""
time complexity O(n)
space complexity O(n)
"""
chars = list(s)
stack = list()
for i in range(len(chars)):
if chars[i].isalpha():
continue
if stack and chars[stack[-1]] == "(" and chars[i] == ")":
stack.pop()
else:
stack.append(i)
for i in range(len(chars) - 1, -1, -1):
if stack and stack[-1] == i:
chars[i] = str()
stack.pop()
return str().join(chars)"""
unit tests
"""
from unittest import TestCase
from algorithms.stacks.minimum_remove_to_make_valid_parentheses.solution import Solution
class SolutionTestCase(TestCase):
def test_zero_unmatched_parentheses(self):
# Given
string = "kt(mnls)hwg(pu(ax)ie)"
solution = Solution()
# When
actual = solution.min_remove_parentheses(string)
# Then
expected = "kt(mnls)hwg(pu(ax)ie)"
self.assertEqual(actual, expected)
def test_some_unmatched_parentheses(self):
# Given
string = "kt(mnls)hwg)pu(ax)ie("
solution = Solution()
# When
actual = solution.min_remove_parentheses(string)
# Then
expected = "kt(mnls)hwgpu(ax)ie"
self.assertEqual(actual, expected)
def test_all_unmatched_parentheses(self):
# Given
string = ")))))((((("
solution = Solution()
# When
actual = solution.min_remove_parentheses(string)
# Then
expected = ""
self.assertEqual(actual, expected)Strategy
Stacks.
Explanation
First, a stack is created. The stack is used to hold the character index of unmatched parentheses in the input string. Next, forward iteration of the characters of the string occurs.
If the current character of the string is an alphabet character, then continue to the next character. If the stack isn’t empty, the top of the stack is an opening parenthesis, and the current character is a closing parenthesis, then the top of the stack is popped since a pair of matched parentheses has been found. Otherwise, push the current character to the top of the stack. After iteration completes, the result is a stack that holds the character index of all unmatched parentheses.
Then, backwards iteration of the characters of the string occurs. If the stack isn’t empty and the top of the stack matches the current index, then one of the unmatched parentheses has been found again. Convert the current character to an empty string, as it will be squashed when the characters are joined as a string. Also pop the top of the stack. After iteration completes, the result is characters of the string with all unmatched parentheses removed.
Time Complexity
The characters of the string are iterated forwards and backwards. Therefore, the time complexity of the algorithm is O(n).
Space Complexity
At worst, all characters of the string are unmatched parentheses. Then, the stack grows to the size of the string. Therefore, the auxiliary space complexity of the algorithm is O(n).
