Daily Challenge 10/09/2024: Minimum Add to Make Parenthesis Valid

Determine the number of parenthesis that need to be added to a string to close all pairs.

Find the full problem on leetcode.

Analysis

This should be trivial, just count the number of unclosed opening parenthesis and closing parenthesis. This should be an easy problem.

()) -> 1 open, 2 closed, requires 1 open.
((( -> 3 open, 0 closed, required 3 closed. 
()(()(( -> 5 open, 2 closed, requires 3 closed.

()))(( 
^ n_opened_unclosed = 1, n_closed_unopened = 0

()))(( 
 ^ n_opened_unclosed = 0, n_closed_unopened = 0
 
()))(( 
  ^ n_opened_unclosed = 0, n_closed_unopened = 1

()))(( 
   ^ n_opened_unclosed = 0, n_closed_unopened = 2

()))(( 
    ^ n_opened_unclosed = 1, n_closed_unopened = 2

()))(( 
    ^ n_opened_unclosed = 2, n_closed_unopened = 2

Algorithm:

1. Iterate over the elements and
   • Count ( everytime one is encountered.
   • When a ) is encountered, count it as unopened if no opening parenthesis have yet been encountered. Otherwise count some ( closed.
2. Return the sum of the unclosed and unopened counts.

This has linear time complexity.

Solution

My solution beat \(93\%\) in terms of runtime and \(71\%\) in terms of memory.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        n_open_unclosed = 0
        n_closed_unopened = 0

        for char in s:
            if char == "(":
                n_open_unclosed += 1
            else:
                # NOTE: There is an opening bracket to close this closing
                #       bracket in the first case.
                if n_open_unclosed > 0:
                    n_open_unclosed -= 1
                else:
                    n_closed_unopened += 1

        return n_open_unclosed + n_closed_unopened