Dada una string de paréntesis válida str que consiste en letras minúsculas, corchetes de apertura y cierre, la tarea es encontrar la string eliminando los corchetes más externos, de modo que la string siga siendo una string de paréntesis válida.
Ejemplos:
Entrada: S = “(((a)(bcd)(e)))”
Salida: (a)(bcd)(e)
Explicación:
Los corchetes más externos son: { S[0], S[1], S [13], S[14] }.
Quitar los corchetes más externos de str modifica str a «(a)(bcd)(e)».
Por lo tanto, la salida requerida es (a)(bcd)(e).Entrada: str = “((ab)(bc))d”
Salida: ((ab)(bc))d
Explicación:
Dado que no hay corchetes más externos presentes en la string. Por lo tanto, la salida requerida es ((ab)(bc))d
Enfoque: la idea es iterar sobre los caracteres de la string y contar el número de paréntesis de apertura y paréntesis de cierre consecutivos desde ambos extremos de la string, respectivamente. Luego, repita los caracteres presentes en la string interna y cuente la cantidad de corchetes de apertura necesarios para equilibrar la string. Siga los pasos a continuación para resolver el problema:
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cnt = 0 , para almacenar el recuento de paréntesis válidos de modo que str[cnt] == '(‘ y str[N – cnt – 1] == ‘)’ .
- Para equilibrar el paréntesis interno de la string con el paréntesis externo, recorra la substring {str[cnt], …, str[N – cnt – 1]} y cuente el mínimo paréntesis de apertura o cierre requerido para equilibrar la substring interna, por ejemplo, cntMinpar .
- Finalmente, actualice cnt += cntMinPair e imprima la substring { str[cnt], …, str[N – cnt] } .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to remove outermost
// enclosing brackets from both end
void removeBrakets(string str)
{
// Stores length of the string
int n = str.length();
// Stores count of parenthesis such
// that str[cnt] == cnt[N - cnt - 1]
int cnt = 0;
// Calculating maximum number of
// bracket pair from the end side
while (cnt < n && str[cnt] == '(' &&
str[n - cnt - 1] == ')')
{
// Update cnt
cnt++;
}
// Stores minimum outer parenthesis
// required to balance the substring
// { str[cnt], ..., [n - cnt -1]
int error = 0;
// Stores count of unbalanced parenthesis
// in { str[cnt], ..., [n - cnt -1]
int open = 0;
// Traverse the substring
// { str[cnt], ..., [n - cnt -1]
for(int i = cnt; i < n - cnt; i++)
{
// If current character is '('
if (str[i] == '(')
{
// Update cntUnbal
open++;
}
// Decrease num, if the current
// character is ')'
else if (str[i] == ')')
{
// Update cntUnbal
if(open>0){
open--;
}
else{
error++;
}
}
}
int rem=cnt-error;
// Print resultant string
cout << str.substr(rem, n - 2*rem) << endl;
}
// Driver Code
int main()
{
// Input string
string str = "((((a)b)(c)))";
removeBrakets(str);
return 0;
}
// This code is contributed by susmitakundugoaldanga
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to remove outermost
// enclosing brackets from both end
static void removeBrakets(String str)
{
// Stores length of the string
int n = str.length();
// Stores count of parenthesis such
// that str[cnt] == cnt[N - cnt - 1]
int cnt = 0;
// Calculating maximum number of
// bracket pair from the end side
while (cnt < n && str.charAt(cnt) == '('
&& str.charAt(n - cnt - 1) == ')') {
// Update cnt
cnt++;
}
// Stores minimum outer parenthesis
// required to balance the substring
// { str[cnt], ..., [n - cnt -1]
int cntMinPar = 0;
// Stores count of unbalanced parenthesis
// in { str[cnt], ..., [n - cnt -1]
int cntUnbal = 0;
// Traverse the substring
// { str[cnt], ..., [n - cnt -1]
for (int i = cnt; i < n - cnt;
i++) {
// If current character is '('
if (str.charAt(i) == '(') {
// Update cntUnbal
cntUnbal++;
}
// Decrease num, if the current
// character is ')'
else if (str.charAt(i) == ')') {
// Update cntUnbal
cntUnbal--;
}
// Update cntMinPar
cntMinPar = Math.min(
cntMinPar, cntUnbal);
}
// Update cnt
cnt += cntMinPar;
// Print resultant string
System.out.println(
str.substring(cnt, n - cnt));
}
// Driver Code
public static void main(
String[] args)
{
// Input string
String str = "((((a)b)(c)))";
removeBrakets(str);
}
}
Python3
# Python3 program to implement
# the above approach
# Function to remove outermost
# enclosing brackets from both end
def removeBrakets(str):
# Stores length of the string
n = len(str)
# Stores count of parenthesis such
# that str[cnt] == cnt[N - cnt - 1]
cnt = 0
# Calculating maximum number of
# bracket pair from the end side
while (cnt < n and str[cnt] == '(' and
str[n - cnt - 1] == ')'):
# Update cnt
cnt += 1
# Stores minimum outer parenthesis
# required to balance the substring
# { str[cnt], ..., [n - cnt -1]
cntMinPar = 0
# Stores count of unbalanced parenthesis
# in { str[cnt], ..., [n - cnt -1]
cntUnbal = 0
# Traverse the substring
# { str[cnt], ..., [n - cnt -1]
for i in range(cnt, n - cnt):
# If current character is '('
if (str[i] == '('):
# Update cntUnbal
cntUnbal += 1
# Decrease num, if the current
# character is ')'
elif str[i] == ')':
# Update cntUnbal
cntUnbal -= 1
# Update cntMinPar
cntMinPar = min(cntMinPar,
cntUnbal)
# Update cnt
cnt += cntMinPar
# Print resultant string
print(str[cnt: n - cnt])
# Driver Code
if __name__ == '__main__':
# Input string
str = "((((a)b)(c)))"
removeBrakets(str)
# This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG {
// Function to remove outermost
// enclosing brackets from both end
static void removeBrakets(String str)
{
// Stores length of the string
int n = str.Length;
// Stores count of parenthesis such
// that str[cnt] == cnt[N - cnt - 1]
int cnt = 0;
// Calculating maximum number of
// bracket pair from the end side
while (cnt < n && str[cnt] == '('
&& str[n - cnt - 1] == ')')
{
// Update cnt
cnt++;
}
// Stores minimum outer parenthesis
// required to balance the substring
// { str[cnt], ..., [n - cnt -1]
int cntMinPar = 0;
// Stores count of unbalanced parenthesis
// in { str[cnt], ..., [n - cnt -1]
int cntUnbal = 0;
// Traverse the substring
// { str[cnt], ..., [n - cnt -1]
for (int i = cnt; i < n - cnt;
i++)
{
// If current character is '('
if (str[i] == '(')
{
// Update cntUnbal
cntUnbal++;
}
// Decrease num, if the current
// character is ')'
else if (str[i] == ')')
{
// Update cntUnbal
cntUnbal--;
}
// Update cntMinPar
cntMinPar = Math.Min(
cntMinPar, cntUnbal);
}
// Update cnt
cnt += cntMinPar;
// Print resultant string
Console.WriteLine(
str.Substring(cnt, n - cnt - 2));
}
// Driver Code
public static void Main(string[] args)
{
// Input string
string str = "((((a)b)(c)))";
removeBrakets(str);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to remove outermost
// enclosing brackets from both end
function removeBrakets(str)
{
// Stores length of the string
var n = str.length;
// Stores count of parenthesis such
// that str[cnt] == cnt[N - cnt - 1]
var cnt = 0;
// Calculating maximum number of
// bracket pair from the end side
while (cnt < n && str[cnt] == '(' &&
str[n - cnt - 1] == ')')
{
// Update cnt
cnt++;
}
// Stores minimum outer parenthesis
// required to balance the substring
// { str[cnt], ..., [n - cnt -1]
var error = 0;
// Stores count of unbalanced parenthesis
// in { str[cnt], ..., [n - cnt -1]
var open = 0;
// Traverse the substring
// { str[cnt], ..., [n - cnt -1]
for(var i = cnt; i < n - cnt; i++)
{
// If current character is '('
if (str[i] == '(')
{
// Update cntUnbal
open++;
}
// Decrease num, if the current
// character is ')'
else if (str[i] == ')')
{
// Update cntUnbal
if (open > 0)
{
open--;
}
else
{
error++;
}
}
}
var rem = cnt - error;
// Print resultant string
document.write(str.substring(
rem, rem + n - 2 * rem));
}
// Driver Code
// Input string
var str = "((((a)b)(c)))";
removeBrakets(str);
// This code is contributed by rutvik_56
</script>
Producción:
((a)b)(c)
Complejidad temporal: O(N)
Espacio auxiliar: O(1)