Minimum Add To Make Parentheses Valid

Minimum Add To Make Parentheses Valid

by

Parentheses are an essential part of mathematical expressions and programming syntax. However, if they are unbalanced, errors can occur. The problem "Minimum Add to Make Parentheses Valid" focuses on determining the smallest number of insertions required to make a given string of parentheses valid.

A valid parentheses string means:

  • Every opening parenthesis ‘(‘ has a corresponding closing parenthesis ‘)’.

  • Parentheses are placed in the correct order.

In this topic, we will explore how to efficiently solve this problem using simple logic and algorithms.

Understanding the Problem

What is a Valid Parentheses String?

A valid parentheses string follows these conditions:

  • Every ( has a matching ).

  • No extra ( or ) exists.

  • The order must be correct.

Examples of valid parentheses strings:
✅ "()", "()()", "(())", "((()))"

Examples of invalid parentheses strings:
❌ ")(", "(()", "())", "((()"

Approach to Solve the Problem

The goal is to determine the minimum number of parentheses that need to be added to make an input string valid.

Key Observations

  • If there are more ( than ), extra ) are needed.

  • If there are more ) than (, extra ( are needed.

  • We must track the balance while traversing the string.

Solution Using a Counter Approach

Algorithm

  1. Initialize two counters:

    • open_needed = 0 → Counts unmatched (.

    • close_needed = 0 → Counts unmatched ).

  2. Traverse the string:

    • If ( appears, increase open_needed.

    • If ) appears:

      • If open_needed > 0, match it with ( (decrease open_needed).

      • Otherwise, increase close_needed (it is an unmatched )).

  3. The total insertions required = open_needed + close_needed.

Implementation in Python

def minAddToMakeValid(s):open_needed = 0close_needed = 0for char in s:if char == '(':open_needed += 1elif char == ')':if open_needed > 0:open_needed -= 1else:close_needed += 1return open_needed + close_needed# Example usageprint(minAddToMakeValid("(()"))  # Output: 1print(minAddToMakeValid("())"))  # Output: 1print(minAddToMakeValid("((("))  # Output: 3print(minAddToMakeValid("()"))   # Output: 0

Explanation of the Code

  • "(()" → Needs 1 closing ) → Output 1.

  • "())" → Needs 1 opening ( → Output 1.

  • "(((" → Needs 3 closing ) → Output 3.

  • "()" → Already valid → Output 0.

The time complexity is O(n) since we iterate through the string once.

Alternative Solution Using a Stack

Another approach is to use a stack to track unmatched parentheses.

Algorithm

  1. Use a stack to store (.

  2. Traverse the string:

    • If (, push to the stack.

    • If ), check the stack:

      • If not empty, pop a ( (valid pair).

      • Otherwise, increase close_needed (unmatched )).

  3. The number of unmatched ( remaining in the stack + close_needed is the result.

Implementation in Python

def minAddToMakeValid(s):stack = []close_needed = 0for char in s:if char == '(':stack.append(char)elif char == ')':if stack:stack.pop()  # Remove a matched '('else:close_needed += 1  # Unmatched ')'return len(stack) + close_needed# Example usageprint(minAddToMakeValid("(()"))  # Output: 1print(minAddToMakeValid("())"))  # Output: 1print(minAddToMakeValid("((("))  # Output: 3print(minAddToMakeValid("()"))   # Output: 0

Complexity Analysis

  • Time Complexity: O(n) (single pass through the string).

  • Space Complexity: O(n) in the worst case (all ( need to be stored).

Comparing Both Approaches

Approach Time Complexity Space Complexity Suitable For
Counter Method O(n) O(1) Best for counting unmatched parentheses efficiently
Stack Method O(n) O(n) Useful when you need to reconstruct the valid sequence

For this problem, the counter method is the most efficient solution.

Example Walkthrough

Let’s analyze some test cases to understand how the algorithm works.

Example 1

Input: "())"

Process:

  1. '(' → open_needed = 1, close_needed = 0

  2. ')' → Match with (, open_needed = 0, close_needed = 0

  3. ')' → No ( left, close_needed = 1

Output: 1

Example 2

Input: "((("

Process:

  1. '(' → open_needed = 1

  2. '(' → open_needed = 2

  3. '(' → open_needed = 3

Output: 3 (needs ))) to balance).

Example 3

Input: ")()("

Process:

  1. ')' → No ( to match, close_needed = 1

  2. '(' → open_needed = 1

  3. ')' → Match with (, open_needed = 0, close_needed = 1

  4. '(' → open_needed = 1

Output: 2 (needs one ( at the beginning and one ) at the end).

Applications of This Problem

1. Syntax Checking in Programming Languages

Languages like Python, Java, and C++ use parentheses for function calls, conditions, and expressions. Detecting unbalanced parentheses is crucial for syntax validation.

2. Compilers and Interpreters

Compilers use parsing algorithms to detect missing or extra parentheses in the code.

3. Expression Validation in Calculators

Online math calculators and scientific applications require balanced parentheses to evaluate expressions correctly.

4. HTML and XML Parsing

Even though HTML/XML uses tags instead of parentheses, the concept of opening and closing elements follows the same principle.

The problem "Minimum Add to Make Parentheses Valid" is essential for validating expressions and detecting errors in syntax.

✅ The counter method is the most efficient with O(n) time complexity and O(1) space complexity.
✅ The stack method is useful for tracking unmatched parentheses but requires O(n) space.
✅ Understanding balanced parentheses helps in fields like compilers, programming languages, and expression validation.

By using efficient algorithms, we can quickly determine the minimum number of insertions needed to make parentheses valid.