Minimum Add to Make Parentheses Valid (medium)

Problem Statement

Given a string str containing '(' and ')' characters, find the minimum number of parentheses that need to be added to a string of parentheses to make it valid.

A valid string of parentheses is one where each opening parenthesis '(' has a corresponding closing parenthesis ')' and vice versa. The goal is to determine the least amount of additions needed to achieve this balance.

Examples

Example 1:
- Input: "(()"
- Expected Output: 1
- Justification: The string has two opening parentheses and one closing parenthesis

.....

Like the course? Get enrolled and start learning!

Davide Pugliese

· 2 years ago

import java.util.Deque;
import java.util.ArrayDeque;
public class Solution {
    // Method to calculate the minimum additions to balance the parentheses
    public int minAddToMakeValid(String S) {
        // ToDO: Write Your Code Here.
        int counter = 0;
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < S.length(); i ++) {
         char c = S.charAt(i);
          if (c == '(') {
            stack.push(c);
          } else if (c == ')' && !stack.isEmpty()) {
            stack.pop();
          } else {
            counter++;
          }        
        }
        return stack.size() + counter;
    }
}

sealess

· 2 years ago

class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        # ToDO: Write Your Code Here.
        stack = []
        for i in S:
            if not stack or i=='(':
                stack.append(i)
            elif i == ')' and stack:
                if stack[-1] != '(':
                    stack.append(i)
                else:
                    stack.pop()

        print(stack)
                
        return len(stack)

Mohammed Dh Abbas

· 2 years ago

# Greedy Solution
class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        count_open = 0 
        count_close = 0
        for char in S:
            if char == '(':
                count_open += 1
            if char == ')' and count_open == 0:
                count_close += 1
            if char == ')' and count_open > 0:
                count_open -= 1
        return count_open + count_close



# Stack Solution
class Solution:
    def minAddToMakeValid(self, S: str) -> int:
        stack = []
        count = 0 
        for char in S:
            if char == "(":
                stack.append("(")
            else:
                if stack and stack[-1] == "(":
                    stack.pop()
                else:
                    count += 1
        return c

Ayush Kumar

· 5 months ago

solved it in 2 mins it must be easy 😭😭😭

class Solution {
public:
int minAddToMakeValid(string s) {
		int open=0,close = 0;
		int res=0;
		for(int i=0;i<s.length();i++){
			if(s[i]=='(')
				open++;
			else{
				if(open>0)
					open--;
				else
					res++;
			}
		}
		return res+open;
}
};