Número mínimo de paréntesis a añadir para que sea válido

Dada una string S de paréntesis ‘(‘ o ‘)’ donde,  . La tarea es encontrar un número mínimo de paréntesis ‘(‘ o ‘)’ (en cualquier posición) que debemos agregar para que la string de paréntesis resultante sea válida.
Ejemplos: 
 

Input: str = "())"
Output: 1
One '(' is required at beginning.

Input: str = "((("
Output: 3
Three ')' is required at end.

Enfoque: mantenemos la pista del equilibrio de la string, es decir, el número de ‘(‘ menos el número de ‘)’. Una string es válida si su saldo es 0 y también cada prefijo tiene un saldo no negativo.
Ahora, considere el saldo de cada prefijo de S. Si alguna vez es negativo (por ejemplo, -1), debemos agregar un paréntesis ‘(‘ al principio. Además, si el saldo de S es positivo (por ejemplo, +P) , debemos agregar corchetes P veces ‘)’ al final.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ Program to find minimum number of '(' or ')'
// must be added to make Parentheses string valid.
#include <bits/stdc++.h>
using namespace std;
 
// Function to return required minimum number
int minParentheses(string p)
{
 
    // maintain balance of string
    int bal = 0;
    int ans = 0;
 
    for (int i = 0; i < p.length(); ++i) {
 
        bal += p[i] == '(' ? 1 : -1;
 
        // It is guaranteed bal >= -1
        if (bal == -1) {
            ans += 1;
            bal += 1;
        }
    }
 
    return bal + ans;
}
 
// Driver code
int main()
{
 
    string p = "())";
 
    // Function to print required answer
    cout << minParentheses(p);
 
    return 0;
}

// Java Program to find minimum number of '(' or ')'
// must be added to make Parentheses string valid.
 
public class GFG {
 
    // Function to return required minimum number
    static int minParentheses(String p)
    {
       
        // maintain balance of string
        int bal = 0;
        int ans = 0;
       
        for (int i = 0; i < p.length(); ++i) {
       
            bal += p.charAt(i) == '(' ? 1 : -1;
       
            // It is guaranteed bal >= -1
            if (bal == -1) {
                ans += 1;
                bal += 1;
            }
        }
       
        return bal + ans;
    }
     
    public static void main(String args[])
    {
        String p = "())";
         
        // Function to print required answer
        System.out.println(minParentheses(p));
       
    }
    // This code is contributed by ANKITRAI1
}

# Python3 Program to find
# minimum number of '(' or ')'
# must be added to make Parentheses
# string valid.
 
# Function to return required
# minimum number
def minParentheses(p):
     
    # maintain balance of string
    bal=0
    ans=0
    for i in range(0,len(p)):
        if(p[i]=='('):
            bal+=1
        else:
            bal+=-1
             
        # It is guaranteed bal >= -1
        if(bal==-1):
            ans+=1
            bal+=1
    return bal+ans
 
# Driver code
if __name__=='__main__':
    p = "())"
     
# Function to print required answer
    print(minParentheses(p))
     
# this code is contributed by
# sahilshelangia

// C# Program to find minimum number
// of '(' or ')' must be added to
// make Parentheses string valid.
using System;
 
class GFG
{
// Function to return required
// minimum number
static int minParentheses(string p)
{
 
    // maintain balance of string
    int bal = 0;
    int ans = 0;
 
    for (int i = 0; i < p.Length; ++i)
    {
 
        bal += p[i] == '(' ? 1 : -1;
 
        // It is guaranteed bal >= -1
        if (bal == -1)
        {
            ans += 1;
            bal += 1;
        }
    }
 
    return bal + ans;
}
 
// Driver code
public static void Main()
{
    string p = "())";
 
    // Function to print required answer
    Console.WriteLine(minParentheses(p));
}
}
 
// This code is contributed
// by Kirti_Mangal

<?php
// PHP Program to find minimum number of
// '(' or ')' must be added to make
// Parentheses string valid.
 
// Function to return required minimum number
function minParentheses($p)
{
 
    // maintain balance of string
    $bal = 0;
    $ans = 0;
 
    for ($i = 0; $i < strlen($p); ++$i)
    {
        if ($p[$i] == '(' )
            $bal += 1 ;
        else
            $bal += -1;
 
        // It is guaranteed bal >= -1
        if ($bal == -1)
        {
            $ans += 1;
            $bal += 1;
        }
    }
 
    return $bal + $ans;
}
 
// Driver code
$p = "())";
 
// Function to print required answer
echo minParentheses($p);
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript Program to find minimum number of '(' or ')'
// must be added to make Parentheses string valid.
 
// Function to return required minimum number
function minParentheses( p)
{
 
    // maintain balance of string
    var bal = 0;
    var ans = 0;
 
    for (var i = 0; i < p.length; ++i) {
 
        bal += p[i] == '(' ? 1 : -1;
 
        // It is guaranteed bal >= -1
        if (bal == -1) {
            ans += 1;
            bal += 1;
        }
    }
 
    return bal + ans;
}
 
var p = "())";
 
// Function to print required answer
document.write( minParentheses(p));
 
// This code is contributed by SoumikMondal
 
</script>

1

Complejidad Temporal: O(N), donde N es la longitud de S. 
Complejidad Espacial: O(1).