Practice/Meta/Leetcode 921. Minimum Add to Make Parentheses Valid

Leetcode 921. Minimum Add to Make Parentheses Valid

CodingMust

Problem

You are given a string containing only the characters '(' and ')'. Your task is to determine the minimum number of parentheses that must be inserted into the string to make it valid.

A valid parentheses string is one where:

• Every opening parenthesis '(' has a corresponding closing parenthesis ')'
• Every closing parenthesis ')' has a corresponding opening parenthesis '(' before it
• Parentheses are properly nested

Return the minimum number of parentheses insertions needed to make the string valid.

Requirements

1. Count how many parentheses need to be added (not removed or replaced)
2. The result should be the minimum possible number of additions
3. Handle empty strings correctly
4. Process strings containing only opening or only closing parentheses

Constraints

• 0 <= s.length <= 1000
• s consists of '(' and ')' only
• Aim for O(n) time complexity where n is the length of the string
• Aim for O(1) space complexity

Examples

Example 1:

Input: s = "())" Output: 1 Explanation: We need to add one opening parenthesis at the beginning to match the extra closing parenthesis. Result: "(())"

Example 2:

Input: s = "(((" Output: 3 Explanation: We need to add three closing parentheses at the end to match all opening parentheses. Result: "((()))"

Example 3:

Input: s = "()" Output: 0 Explanation: The string is already valid, no additions needed.

Example 4:

Input: s = "()))((" Output: 4 Explanation: We need one opening parenthesis for the unmatched closing at position 2, and two closing parentheses for the unmatched opening ones at the end. We also need one opening for the closing at position 3. Total: 4 additions needed.