Dada una secuencia de paréntesis balanceada como una string str que contiene el carácter ‘(‘ o ‘)’ , la tarea es encontrar la siguiente secuencia balanceada de orden lexicográfico si es posible, sino imprime -1 .
Ejemplos:
Entrada: str = “(())”
Salida:()()
Entrada: str = “((()))”
Salida: (()())
Enfoque: primero encuentre el corchete de apertura más a la derecha que podemos reemplazar por un corchete de cierre para obtener la string de corchetes lexicográficamente más grande. La string actualizada podría no estar balanceada, podemos llenar la parte restante de la string con la lexicográficamente mínima: es decir, primero con tantos corchetes de apertura como sea posible, y luego llenar las posiciones restantes con corchetes de cierre. En otras palabras, tratamos de dejar un prefijo lo más largo posible sin cambios, y el sufijo se reemplaza por el mínimo lexicográficamente.
Para encontrar esta posición, podemos iterar sobre el carácter de derecha a izquierda y mantener el equilibrio de profundidad de los corchetes abiertos y cerrados. Cuando nos encontramos con un paréntesis de apertura, disminuiremos la profundidad, y cuando nos encontremos con un paréntesis de cierre, la aumentaremos. Si en algún momento nos encontramos con un paréntesis de apertura, y el saldo después de procesar este símbolo es positivo, entonces hemos encontrado la posición más a la derecha que podemos cambiar. Cambiamos el símbolo, calculamos el número de paréntesis de apertura y cierre que tenemos que agregar al lado derecho y los organizamos de la manera lexicográficamente mínima.
Si no encontramos una posición adecuada, entonces esta secuencia ya es la máxima posible y no hay respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the lexicographically
// next balanced bracket
// expression if possible
string next_balanced_sequence(string& s)
{
string next = "-1";
int length = s.size();
int depth = 0;
for (int i = length - 1; i >= 0; --i) {
// Decrement the depth for
// every opening bracket
if (s[i] == '(')
depth--;
// Increment for the
// closing brackets
else
depth++;
// Last opening bracket
if (s[i] == '(' && depth > 0) {
depth--;
int open = (length - i - 1 - depth) / 2;
int close = length - i - 1 - open;
// Generate the required string
next = s.substr(0, i) + ')'
+ string(open, '(')
+ string(close, ')');
break;
}
}
return next;
}
// Driver code
int main()
{
string s = "((()))";
cout << next_balanced_sequence(s);
return 0;
}
Java
// Java implementation of the approach
class Sol
{
// makes a string containing char d
// c number of times
static String string(int c, char d)
{
String s = "";
for(int i = 0; i < c; i++)
s += d;
return s;
}
// Function to find the lexicographically
// next balanced bracket
// expression if possible
static String next_balanced_sequence(String s)
{
String next = "-1";
int length = s.length();
int depth = 0;
for (int i = length - 1; i >= 0; --i)
{
// Decrement the depth for
// every opening bracket
if (s.charAt(i) == '(')
depth--;
// Increment for the
// closing brackets
else
depth++;
// Last opening bracket
if (s.charAt(i) == '(' && depth > 0)
{
depth--;
int open = (length - i - 1 - depth) / 2;
int close = length - i - 1 - open;
// Generate the required String
next = s.substring(0, i) + ')'
+ string(open, '(')
+ string(close, ')');
break;
}
}
return next;
}
// Driver code
public static void main(String args[])
{
String s = "((()))";
System.out.println(next_balanced_sequence(s));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach
# Function to find the lexicographically
# next balanced bracket
# expression if possible
def next_balanced_sequence(s) :
next = "-1";
length = len(s);
depth = 0;
for i in range(length - 1, -1, -1) :
# Decrement the depth for
# every opening bracket
if (s[i] == '(') :
depth -= 1;
# Increment for the
# closing brackets
else :
depth += 1;
# Last opening bracket
if (s[i] == '(' and depth > 0) :
depth -= 1;
open = (length - i - 1 - depth) // 2;
close = length - i - 1 - open;
# Generate the required string
next = s[0 : i] + ')' + open * '(' + close* ')';
break;
return next;
# Driver code
if __name__ == "__main__" :
s = "((()))";
print(next_balanced_sequence(s));
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// makes a string containing char d
// c number of times
static String strings(int c, char d)
{
String s = "";
for(int i = 0; i < c; i++)
s += d;
return s;
}
// Function to find the lexicographically
// next balanced bracket
// expression if possible
static String next_balanced_sequence(String s)
{
String next = "-1";
int length = s.Length;
int depth = 0;
for (int i = length - 1; i >= 0; --i)
{
// Decrement the depth for
// every opening bracket
if (s[i] == '(')
depth--;
// Increment for the
// closing brackets
else
depth++;
// Last opening bracket
if (s[i] == '(' && depth > 0)
{
depth--;
int open = (length - i - 1 - depth) / 2;
int close = length - i - 1 - open;
// Generate the required String
next = s.Substring(0, i) + ')' +
strings(open, '(') +
strings(close, ')');
break;
}
}
return next;
}
// Driver code
public static void Main(String []args)
{
String s = "((()))";
Console.WriteLine(next_balanced_sequence(s));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// makes a string containing char d
// c number of times
function string(c, d)
{
let s = "";
for(let i = 0; i < c; i++)
s += d;
return s;
}
// Function to find the lexicographically
// next balanced bracket
// expression if possible
function next_balanced_sequence(s)
{
let next = "-1";
let length = s.length;
let depth = 0;
for (let i = length - 1; i >= 0; --i)
{
// Decrement the depth for
// every opening bracket
if (s[i] == '(')
depth--;
// Increment for the
// closing brackets
else
depth++;
// Last opening bracket
if (s[i] == '(' && depth > 0)
{
depth--;
let open = (length - i - 1 - depth) / 2;
let close = length - i - 1 - open;
// Generate the required String
next = s.substr(0, i) + ')'
+ string(open, '(')
+ string(close, ')');
break;
}
}
return next;
}
// Driver Code
let s = "((()))";
document.write(next_balanced_sequence(s));
// This code is contributed by sanjoy_62.
</script>
(()())