Compruebe si la secuencia de corchetes se puede equilibrar con al menos un cambio en la posición de un corchete

Dada una secuencia de paréntesis desequilibrada como una string str , la tarea es encontrar si la string dada se puede equilibrar moviendo como máximo un paréntesis de su lugar original en la secuencia a cualquier otra posición.
Ejemplos: 
 

Entrada: str = “)(()” 
Salida: Sí 
Como mover s[0] al final lo hará válido. 
“(())”
Entrada: str = “()))(()” 
Salida: No 
 

Enfoque: Considere X como un corchete válido, entonces definitivamente (X) también es válido. Si X no es válido y se puede equilibrar con un solo cambio de posición en algún paréntesis, entonces debe ser del tipo X = “)(“ donde ‘)’ se ha colocado antes de ‘(‘ . 
Ahora, X se puede reemplazar con ( X) ya que no afectará la naturaleza balanceada de X. La nueva string se convierte en X = «()()» que está balanceada. 
Por lo tanto, si (X) está balanceada, entonces podemos decir que X puede balancearse como máximo con una cambio en la posición de algún soporte.
A continuación se muestra la implementación del enfoque anterior:
 

// CPP implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if the sequence
// can be balanced by changing the
// position of at most one bracket
bool canBeBalanced(string s, int n)
{
    // Odd length string can
    // never be balanced
    if (n % 2 == 1)
        return false;
 
    // Add '(' in the beginning and ')'
    // in the end of the string
    string k = "(";
    k += s + ")";
 
    vector<string> d;
    int cnt = 0;
 
    for (int i = 0; i < k.length(); i++)
    {
        // If its an opening bracket then
        // append it to the temp string
        if (k[i] == '(')
            d.push_back("(");
 
        // If its a closing bracket
        else
        {
            // There was an opening bracket
            // to match it with
            if (d.size() != 0)
                d.pop_back();
 
            // No opening bracket to
            // match it with
            else
                return false;
        }
    }
 
    // Sequence is balanced
    if (d.empty())
        return true;
    return false;
}
 
// Driver Code
int main(int argc, char const *argv[])
{
    string s = ")(()";
    int n = s.length();
 
    (canBeBalanced(s, n)) ? cout << "Yes"
                  << endl : cout << "No" << endl;
    return 0;
}
 
// This code is contributed by
// sanjeev2552

// Java implementation of the approach
import java.util.Vector;
 
class GFG
{
 
    // Function that returns true if the sequence
    // can be balanced by changing the
    // position of at most one bracket
    static boolean canBeBalanced(String s, int n)
    {
 
        // Odd length string can
        // never be balanced
        if (n % 2 == 1)
            return false;
 
        // Add '(' in the beginning and ')'
        // in the end of the string
        String k = "(";
        k += s + ")";
        Vector<String> d = new Vector<>();
 
        for (int i = 0; i < k.length(); i++)
        {
 
            // If its an opening bracket then
            // append it to the temp string
            if (k.charAt(i) == '(')
                d.add("(");
 
            // If its a closing bracket
            else
            {
 
                // There was an opening bracket
                // to match it with
                if (d.size() != 0)
                    d.remove(d.size() - 1);
 
                // No opening bracket to
                // match it with
                else
                    return false;
            }
        }
 
        // Sequence is balanced
        if (d.isEmpty())
            return true;
        return false;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String s = ")(()";
        int n = s.length();
 
        if (canBeBalanced(s, n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 implementation of the approach
 
# Function that returns true if the sequence
# can be balanced by changing the
# position of at most one bracket
def canBeBalanced(s, n):
 
    # Odd length string can
    # never be balanced
    if n % 2 == 1:
        return False
 
    # Add '(' in the beginning and ')'
    # in the end of the string
    k = "("
    k = k + s+")"
    d = []
    count = 0
    for i in range(len(k)):
 
        # If its an opening bracket then
        # append it to the temp string
        if k[i] == "(":
            d.append("(")
 
        # If its a closing bracket
        else:
 
            # There was an opening bracket
            # to match it with
            if len(d)!= 0:
                d.pop()
 
            # No opening bracket to
            # match it with
            else:
                return False
     
    # Sequence is balanced
    if len(d) == 0:
        return True
    return False
 
# Driver code
S = ")(()"
n = len(S)
if(canBeBalanced(S, n)):
    print("Yes")
else:
    print("No")

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function that returns true if the sequence
    // can be balanced by changing the
    // position of at most one bracket
    static bool canBeBalanced(string s, int n)
    {
 
        // Odd length string can
        // never be balanced
        if (n % 2 == 1)
            return false;
 
        // Add '(' in the beginning and ')'
        // in the end of the string
        string k = "(";
        k += s + ")";
        List<string> d = new List<string>();
 
        for (int i = 0; i < k.Length; i++)
        {
 
            // If its an opening bracket then
            // append it to the temp string
            if (k[i] == '(')
                d.Add("(");
 
            // If its a closing bracket
            else
            {
 
                // There was an opening bracket
                // to match it with
                if (d.Count != 0)
                    d.RemoveAt(d.Count - 1);
 
                // No opening bracket to
                // match it with
                else
                    return false;
            }
        }
 
        // Sequence is balanced
        if (d.Count == 0)
            return true;
        return false;
    }
 
    // Driver Code
    public static void Main()
    {
        string s = ")(()";
        int n = s.Length;
 
        if (canBeBalanced(s, n))
            Console.Write("Yes");
        else
            Console.Write("No");
    }
}
 
// This code is contributed by
// mohit kumar 29

<script>
 
// JavaScript implementation of the approach
 
// Function that returns true if the sequence
    // can be balanced by changing the
    // position of at most one bracket
function canBeBalanced(s,n)
{
    // Odd length string can
        // never be balanced
        if (n % 2 == 1)
            return false;
   
        // Add '(' in the beginning and ')'
        // in the end of the string
        let k = "(";
        k += s + ")";
        let d = [];
   
        for (let i = 0; i < k.length; i++)
        {
   
            // If its an opening bracket then
            // append it to the temp string
            if (k[i] == '(')
                d.push("(");
   
            // If its a closing bracket
            else
            {
   
                // There was an opening bracket
                // to match it with
                if (d.length != 0)
                    d.pop();
   
                // No opening bracket to
                // match it with
                else
                    return false;
            }
        }
   
        // Sequence is balanced
        if (d.length==0)
            return true;
        return false;
}
 
// Driver Code
let s = ")(()";
        let n = s.length;
   
        if (canBeBalanced(s, n))
            document.write("Yes");
        else
            document.write("No");
 
 
// This code is contributed by unknown2108
 
</script>

Yes

Complejidad de tiempo: O (n), donde n es el tamaño de la string dada

Complejidad espacial : O(n)