921. Minimum Add to Make Parentheses Valid

MediumView on LeetCode

String Stack Greedy

Time: O(n)

Space: O(n)

Problem Overview

Scan left to right maintaining how many unmatched opening parentheses remain.

Intuition

Scan left to right maintaining how many unmatched opening parentheses remain. A closing bracket without a matching open must be fixed by inserting an open earlier; leftover opens need closing brackets appended. Minimum additions = unmatched opens + unmatched closes.

Algorithm

1Initialize open = 0, close = 0.
2For each char: if '(', open++. If ')' and open > 0, open-- (match). Else close++ (unmatched close).
3Return open + close.

Example Walkthrough

Input: s = "())"

1.'(' → open=1. ')' → open=0. ')' → close=1 (no open to match).
2.Need 1 insert for extra close; 0 leftover opens.

Output: 1

Common Pitfalls

•Greedy: always match a close with the nearest pending open.
•Do not count matched pairs toward additions.
•Empty string needs 0 additions.

921.cs

// Approach: Use a stack; unmatched '(' and ')' characters remain; the stack size at the end equals the number of additions needed.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MinAddToMakeValid(string s)
    {
        Stack<char> st = new Stack<char>();
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(')
                st.Push(s[i]);
            else
            {
                if (st.Count > 0 && st.Peek() == '(')
                    st.Pop();
                else
                    st.Push(s[i]);
            }
        }

        return st.Count;
    }
}

Was this solution helpful?