Min Add to Make Parentheses Valid

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Minimum additions to make parenthesis string valid.

See our study guide for structured GFG and LeetCode practice.

Intuition

Minimum additions to make parenthesis string valid. Track open count and close needed.

Algorithm

1Scan: open++ for (, open-- for ) if open>0 else close++. Answer = open + close.

Common Pitfalls

• Same as LC 921. Track unmatched ( and unmatched ). At end: both counts added give minimum additions.

Min Add to Make Parentheses Valid.java

Java

// Approach: Track open brackets needed and close brackets needed. On '(' increment open; on ')' decrement or increment close.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int minParentheses(String s) {
        Stack<Character> st = new Stack<>();
        int count = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '(')
                st.push(ch);
            else {
                if (!st.isEmpty())
                    st.pop();
                else
                    count++;
            }
        }
        return st.isEmpty() ? count : count + st.size();
    }
}

Was this solution helpful?