# 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:

- 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.

- Count
- 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:
= 0
n_open_unclosed = 0
n_closed_unopened
for char in s:
if char == "(":
+= 1
n_open_unclosed else:
# NOTE: There is an opening bracket to close this closing
# bracket in the first case.
if n_open_unclosed > 0:
-= 1
n_open_unclosed else:
+= 1
n_closed_unopened
return n_open_unclosed + n_closed_unopened
```