Leetcode Daily Question 09/10/2024 - 921. Minimum Add to Make Parentheses Valid

Problem Description:

A parentheses string is valid if and only if: ————————————————————— It is the empty string, 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. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. ————————————————————— For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))". Return the minimum number of moves required to make s valid.

class Solution:
  def minAddToMakeValid(self, s: str):
    unmatched_closed = 0
    unmatched_open = 0
    
    for char in s:
      if char == "(":
        unmatched_open += 1
      else:
        if unmatched_open > 0:
          unmatched_open -= 1
        else:
          unmatched_closed += 1
    
    return unmatched_closed + unmatched_open

Explanation:

To solve this, we need to find out how many unmatched open/closed parenthesis there are. We can use a stack-like counting method to save space.

Everytime we see an open parenthesis, we add 1 to the unmatched_open counter. If ever we see a closed parenthesis and unmatched_open is not 0, we have found a valid match.

If none of these cases match, that must mean we have an unmatched_closed parenthesis.

def minAddToMakeValid(s):
  unmatched_open = 0
  unmatched_closed = 0
  
  for char in s:
    if char == "(":
      unmatched_open += 1
    else:
      if unmatched_open > 0:
        unmatched_open -= 1
      else:
        unmatched_closed += 1
  
  return unmatched_open + unmatched_closed

The time complexity is O(n) as we traverse the string exactly once.

The space complexity is O(1) as we only store constant variables.

The full solution can be found near the top of the page.