Dada una string str , la tarea es encontrar el número máximo de pares (str[i], str[j]) de paréntesis equilibrados necesarios para eliminar de modo que la string no contenga ninguna subsecuencia de paréntesis equilibrados:
Ejemplos:
Entrada: str = “{(})”
Salida: 2
Explicación:
Eliminando el par de paréntesis válidos (0, 2) modificó str a “()”
Eliminando el par de paréntesis válidos (0, 1) modificó str a “”.
Ahora, str no contiene ningún paréntesis válido. La salida requerida es 2.Entrada: str = “)}(}”
Salida: 0
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inicialice tres variables, digamos cntSqr , cntCurly y cntSml , para almacenar el conteo de paréntesis válidos “[”, el conteo de paréntesis válidos “{}” y el conteo de paréntesis válidos pequeños respectivamente.
- Inicialice una variable, digamos cntPairs , para almacenar el recuento de pares de paréntesis equilibrados que se deben eliminar de modo que la string no contenga ninguna subsecuencia de paréntesis equilibrados.
- Itere sobre los caracteres de la string y verifique las siguientes condiciones:
- Si str[i] == ‘(‘ , incremente el valor de cntSml en 1 .
- Si str[i] = ‘{‘ , incremente el valor de cntCurly en 1 .
- Si str[i] = ‘[‘ , incremente el valor de cntSqr en 1 .
- Si str[i] = ‘]’ , compruebe si cntSqr es mayor que 0 o no. Si se determina que es cierto, disminuya el valor de cntSqr en 1 e incremente el valor de cntPairs en 1 .
- Si str[i] = ‘}’ , compruebe si cntCurly es mayor que 0 o no. Si se determina que es cierto, disminuya el valor de cntCurly en 1 e incremente el valor de cntPairs en 1 .
- Si str[i] = ‘)’ , compruebe si cntSml es mayor que 0 o no. Si se determina que es cierto, disminuya el valor de cntSml en 1 e incremente el valor de cntPairs en 1 .
- Finalmente, imprima el valor de cntPairs .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
// Function to find the maximum count of pairs
// required to be removed such that subsequence
// of string does not contain any valid parenthesis
void cntBalancedParenthesis(string s, int N)
{
// Stores count of pairs
// of balanced parenthesis
int cntPairs = 0;
// Stores count of curly
// balanced parenthesis
int cntCurly = 0;
// Stores count of small
// balanced parenthesis
int cntSml = 0;
// Stores count of square
// balanced parenthesis
int cntSqr = 0;
// Iterate over characters
// of the string
for (int i = 0; i < N; i++) {
if (s[i] == '{') {
// Update cntCurly
cntCurly++;
}
else if (s[i] == '(') {
// Update cntSml
cntSml++;
}
else if (s[i] == '[') {
// Update cntSqr
cntSqr++;
}
else if (s[i] == '}' && cntCurly > 0) {
// Update cntCurly
cntCurly--;
// Update cntPairs
cntPairs++;
}
else if (s[i] == ')' && cntSml > 0) {
// Update cntSml
cntSml--;
// Update cntPairs
cntPairs++;
}
else if (s[i] == ']' && cntSqr > 0) {
// Update cntSml
cntSqr--;
// Update cntPairs
cntPairs++;
}
}
cout << cntPairs;
}
// Driver Code
int main()
{
// Given String
string s = "{(})";
int N = s.length();
// Function call
cntBalancedParenthesis(s, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG
{
// Function to find the maximum count of pairs
// required to be removed such that subsequence
// of string does not contain any valid parenthesis
static void cntBalancedParenthesis(String s, int N)
{
// Stores count of pairs
// of balanced parenthesis
int cntPairs = 0;
// Stores count of curly
// balanced parenthesis
int cntCurly = 0;
// Stores count of small
// balanced parenthesis
int cntSml = 0;
// Stores count of square
// balanced parenthesis
int cntSqr = 0;
// Iterate over characters
// of the string
for (int i = 0; i < N; i++) {
if (s.charAt(i) == '{')
{
// Update cntCurly
cntCurly++;
}
else if (s.charAt(i) == '(')
{
// Update cntSml
cntSml++;
}
else if (s.charAt(i) == '[')
{
// Update cntSqr
cntSqr++;
}
else if (s.charAt(i) == '}' && cntCurly > 0)
{
// Update cntCurly
cntCurly--;
// Update cntPairs
cntPairs++;
}
else if (s.charAt(i) == ')' && cntSml > 0)
{
// Update cntSml
cntSml--;
// Update cntPairs
cntPairs++;
}
else if (s.charAt(i) == ']' && cntSqr > 0)
{
// Update cntSml
cntSqr--;
// Update cntPairs
cntPairs++;
}
}
System.out.println(cntPairs);
}
// Driver Code
public static void main(String[] args)
{
// Given String
String s = "{(})";
int N = s.length();
// Function call
cntBalancedParenthesis(s, N);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python program to implement
# the above approach
# Function to find the maximum count of pairs
# required to be removed such that subsequence
# of string does not contain any valid parenthesis
def cntBalancedParenthesis(s, N):
# Stores count of pairs
# of balanced parenthesis
cntPairs = 0;
# Stores count of curly
# balanced parenthesis
cntCurly = 0;
# Stores count of small
# balanced parenthesis
cntSml = 0;
# Stores count of square
# balanced parenthesis
cntSqr = 0;
# Iterate over characters
# of the string
for i in range(N):
if (ord(s[i]) == ord('{')):
# Update cntCurly
cntCurly += 1;
elif (ord(s[i]) == ord('(')):
# Update cntSml
cntSml += 1;
elif (ord(s[i]) == ord('[')):
# Update cntSqr
cntSqr += 1;
elif (ord(s[i]) == ord('}') and cntCurly > 0):
# Update cntCurly
cntCurly -=1;
# Update cntPairs
cntPairs += 1;
elif (ord(s[i]) == ord(')') and cntSml > 0):
# Update cntSml
cntSml -=1;
# Update cntPairs
cntPairs += 1;
elif (ord(s[i]) == ord(']') and cntSqr > 0):
# Update cntSml
cntSqr -=1;
# Update cntPairs
cntPairs += 1;
print(cntPairs);
# Driver Code
if __name__ == '__main__':
# Given String
s = "{(})";
N = len(s);
# Function call
cntBalancedParenthesis(s, N);
# This code is contributed by 29AjayKumar
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the maximum count of pairs
// required to be removed such that subsequence
// of string does not contain any valid parenthesis
static void cntBalancedParenthesis(String s, int N)
{
// Stores count of pairs
// of balanced parenthesis
int cntPairs = 0;
// Stores count of curly
// balanced parenthesis
int cntCurly = 0;
// Stores count of small
// balanced parenthesis
int cntSml = 0;
// Stores count of square
// balanced parenthesis
int cntSqr = 0;
// Iterate over characters
// of the string
for (int i = 0; i < N; i++) {
if (s[i] == '{') {
// Update cntCurly
cntCurly++;
}
else if (s[i] == '(') {
// Update cntSml
cntSml++;
}
else if (s[i] == '[') {
// Update cntSqr
cntSqr++;
}
else if (s[i] == '}' && cntCurly > 0) {
// Update cntCurly
cntCurly--;
// Update cntPairs
cntPairs++;
}
else if (s[i] == ')' && cntSml > 0) {
// Update cntSml
cntSml--;
// Update cntPairs
cntPairs++;
}
else if (s[i] == ']' && cntSqr > 0) {
// Update cntSml
cntSqr--;
// Update cntPairs
cntPairs++;
}
}
Console.WriteLine(cntPairs);
}
// Driver Code
static public void Main()
{
// Given String
String s = "{(})";
int N = s.Length;
// Function call
cntBalancedParenthesis(s, N);
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the maximum count of pairs
// required to be removed such that subsequence
// of string does not contain any valid parenthesis
function cntBalancedParenthesis( s , N)
{
// Stores count of pairs
// of balanced parenthesis
var cntPairs = 0;
// Stores count of curly
// balanced parenthesis
var cntCurly = 0;
// Stores count of small
// balanced parenthesis
var cntSml = 0;
// Stores count of square
// balanced parenthesis
var cntSqr = 0;
// Iterate over characters
// of the string
for (i = 0; i < N; i++) {
if (s.charAt(i) == '{')
{
// Update cntCurly
cntCurly++;
}
else if (s.charAt(i) == '(')
{
// Update cntSml
cntSml++;
}
else if (s.charAt(i) == '[')
{
// Update cntSqr
cntSqr++;
}
else if (s.charAt(i) == '}' && cntCurly > 0)
{
// Update cntCurly
cntCurly--;
// Update cntPairs
cntPairs++;
}
else if (s.charAt(i) == ')' && cntSml > 0)
{
// Update cntSml
cntSml--;
// Update cntPairs
cntPairs++;
}
else if (s.charAt(i) == ']' && cntSqr > 0)
{
// Update cntSml
cntSqr--;
// Update cntPairs
cntPairs++;
}
}
document.write(cntPairs);
}
// Driver Code
// Given String
var s = "{(})";
var N = s.length;
// Function call
cntBalancedParenthesis(s, N);
// This code is contributed by todaysgaurav
</script>
Producción:
2
Complejidad de tiempo: O(N) donde n es el número de elementos en una string dada. Como estamos usando un bucle para atravesar N veces, nos costará O (N) tiempo
Espacio auxiliar: O (1), ya que no estamos usando espacio adicional.
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA