Dada una string S , encuentre la longitud de la subsecuencia balanceada más larga en ella. Una string balanceada se define como: –
- Una string nula es una string balanceada.
- Si X e Y son strings balanceadas, entonces (X)Y y XY son strings balanceadas.
Ejemplos:
Input : S = "()())" Output : 4 ()() is the longest balanced subsequence of length 4. Input : s = "()(((((()" Output : 4
Enfoque 1:
Un enfoque de fuerza bruta es encontrar todas las subsecuencias de la string S dada y verificar todas las subsecuencias posibles si forman una secuencia balanceada. En caso afirmativo, compárelo con el valor máximo.
El mejor enfoque es utilizar la programación dinámica .
La subsecuencia equilibrada más larga (LBS), se puede definir recursivamente como se muestra a continuación.
LBS of substring str[i..j] :
If str[i] == str[j]
LBS(str, i, j) = LBS(str, i + 1, j - 1) + 2
Else
LBS(str, i, j) = max(LBS(str, i, k) +
LBS(str, k + 1, j))
Where i <= k < j
Declare una array 2D dp[][], donde nuestro estado dp[i][j] denotará la longitud de la subsecuencia balanceada más larga del índice i al j. Calcularemos este estado en orden creciente de j – i. Para un estado particular dp[i][j], intentaremos hacer coincidir el símbolo j-ésimo con el símbolo k-ésimo. Eso solo se puede hacer si S[k] es ‘(‘ y S[j] es ‘)’. Tomaremos el máximo de 2 + dp[i][k – 1] + dp[k + 1][j – 1] para todos los k posibles y también max(dp[i + 1][j], dp[ i][j – 1]) y poner el valor en dp[i][j]. De esta forma, podemos llenar todos los estados de dp. dp[0][longitud de la string – 1] (considerando la indexación 0) será nuestra respuesta.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find length of
// the longest balanced subsequence
#include <bits/stdc++.h>
using namespace std;
int maxLength(char s[], int n)
{
int dp[n][n];
memset(dp, 0, sizeof(dp));
// Considering all balanced
// substrings of length 2
for (int i = 0; i < n - 1; i++)
if (s[i] == '(' && s[i + 1] == ')')
dp[i][i + 1] = 2;
// Considering all other substrings
for (int l = 2; l < n; l++) {
for (int i = 0, j = l; j < n; i++, j++) {
if (s[i] == '(' && s[j] == ')')
dp[i][j] = 2 + dp[i + 1][j - 1];
for (int k = i; k < j; k++)
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k + 1][j]);
}
}
return dp[0][n - 1];
}
// Driver Code
int main()
{
char s[] = "()(((((()";
int n = strlen(s);
cout << maxLength(s, n) << endl;
return 0;
}
Java
// Java program to find length of the
// longest balanced subsequence.
import java.io.*;
class GFG {
static int maxLength(String s, int n)
{
int dp[][] = new int[n][n];
// Considering all balanced substrings
// of length 2
for (int i = 0; i < n - 1; i++)
if (s.charAt(i) == '(' && s.charAt(i + 1) == ')')
dp[i][i + 1] = 2;
// Considering all other substrings
for (int l = 2; l < n; l++) {
for (int i = 0, j = l; j < n; i++, j++) {
if (s.charAt(i) == '(' && s.charAt(j) == ')')
dp[i][j] = 2 + dp[i + 1][j - 1];
for (int k = i; k < j; k++)
dp[i][j] = Math.max(dp[i][j],
dp[i][k] + dp[k + 1][j]);
}
}
return dp[0][n - 1];
}
// Driver Code
public static void main(String[] args)
{
String s = "()(((((()";
int n = s.length();
System.out.println(maxLength(s, n));
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 program to find length of
# the longest balanced subsequence
def maxLength(s, n):
dp = [[0 for i in range(n)]
for i in range(n)]
# Considering all balanced
# substrings of length 2
for i in range(n - 1):
if (s[i] == '(' and s[i + 1] == ')'):
dp[i][i + 1] = 2
# Considering all other substrings
for l in range(2, n):
i = -1
for j in range(l, n):
i += 1
if (s[i] == '(' and s[j] == ')'):
dp[i][j] = 2 + dp[i + 1][j - 1]
for k in range(i, j):
dp[i][j] = max(dp[i][j], dp[i][k] +
dp[k + 1][j])
return dp[0][n - 1]
# Driver Code
s = "()(((((()"
n = len(s)
print(maxLength(s, n))
# This code is contributed
# by sahishelangia
C#
// C# program to find length of the
// longest balanced subsequence.
using System;
class GFG {
static int maxLength(String s, int n)
{
int[, ] dp = new int[n, n];
// Considering all balanced substrings
// of length 2
for (int i = 0; i < n - 1; i++)
if (s[i] == '(' && s[i + 1] == ')')
dp[i, i + 1] = 2;
// Considering all other substrings
for (int l = 2; l < n; l++) {
for (int i = 0, j = l; j < n; i++, j++) {
if (s[i] == '(' && s[j] == ')')
dp[i, j] = 2 + dp[i + 1, j - 1];
for (int k = i; k < j; k++)
dp[i, j] = Math.Max(dp[i, j],
dp[i, k] + dp[k + 1, j]);
}
}
return dp[0, n - 1];
}
// Driver Code
public static void Main()
{
string s = "()(((((()";
int n = s.Length;
Console.WriteLine(maxLength(s, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find length of
// the longest balanced subsequence
function maxLength($s, $n)
{
$dp = array_fill(0, $n,
array_fill(0, $n, NULL));
// Considering all balanced
// substrings of length 2
for ($i = 0; $i < $n - 1; $i++)
if ($s[$i] == '(' && $s[$i + 1] == ')')
$dp[$i][$i + 1] = 2;
// Considering all other substrings
for ($l = 2; $l < $n; $l++)
{
for ($i = 0, $j = $l; $j < $n; $i++, $j++)
{
if ($s[$i] == '(' && $s[$j] == ')')
$dp[$i][$j] = 2 + $dp[$i + 1][$j - 1];
for ($k = $i; $k < $j; $k++)
$dp[$i][$j] = max($dp[$i][$j],
$dp[$i][$k] +
$dp[$k + 1][$j]);
}
}
return $dp[0][$n - 1];
}
// Driver Code
$s = "()(((((()";
$n = strlen($s);
echo maxLength($s, $n)."\n";
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to find length of the
// longest balanced subsequence.
function maxLength(s, n)
{
let dp = new Array(n);
for (let i = 0; i < n; i++)
{
dp[i] = new Array(n);
for (let j = 0; j < n; j++)
{
dp[i][j] = 0;
}
}
// Considering all balanced substrings
// of length 2
for (let i = 0; i < n - 1; i++)
if (s[i] == '(' && s[i + 1] == ')')
dp[i][i + 1] = 2;
// Considering all other substrings
for (let l = 2; l < n; l++) {
for (let i = 0, j = l; j < n; i++, j++) {
if (s[i] == '(' && s[j] == ')')
dp[i][j] = 2 + dp[i + 1][j - 1];
for (let k = i; k < j; k++)
dp[i][j] = Math.max(dp[i][j],
dp[i][k] + dp[k + 1][j]);
}
}
return dp[0][n - 1];
}
let s = "()(((((()";
let n = s.length;
document.write(maxLength(s, n));
</script>
Producción:
4
Complejidad de Tiempo : O(n 2 )
Espacio Auxiliar : O(n 2 )
Enfoque 2: Este enfoque resuelve el problema de una manera más eficiente.
- Cuente la cantidad de llaves que se eliminarán para obtener la subsecuencia de paréntesis balanceada más larga.
- Si el número de índice i-th de llaves cerradas es mayor que el número de llaves abiertas, entonces esa llave cerrada debe eliminarse.
- Cuente el número de aparatos ortopédicos cerrados que deben quitarse.
- Al final, también se eliminará la cantidad de llaves abiertas adicionales.
- Por lo tanto, el recuento total que se eliminará sería la suma de las llaves abiertas adicionales y las llaves cerradas no válidas.
Implementación:
C++
// C++ program to find length of
// the longest balanced subsequence
#include <bits/stdc++.h>
using namespace std;
int maxLength(char s[], int n)
{
// As it's subsequence - assuming first
// open brace would map to a first close
// brace which occurs after the open brace
// to make subsequence balanced and second
// open brace would map to second close
// brace and so on.
// Variable to count all the open brace
// that does not have the corresponding
// closing brace.
int invalidOpenBraces = 0;
// To count all the close brace that
// does not have the corresponding open brace.
int invalidCloseBraces = 0;
// Iterating over the String
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
// Number of open braces that
// hasn't been closed yet.
invalidOpenBraces++;
}
else {
if (invalidOpenBraces == 0) {
// Number of close braces that
// cannot be mapped to any open
// brace.
invalidCloseBraces++;
}
else {
// Mapping the ith close brace
// to one of the open brace.
invalidOpenBraces--;
}
}
}
return (
n - (invalidOpenBraces
+ invalidCloseBraces));
}
// Driver Code
int main()
{
char s[] = "()(((((()";
int n = strlen(s);
cout << maxLength(s, n) << endl;
return 0;
}
Java
// Java program to find the length of the
// longest balanced subsequence.
import java.io.*;
class GFG {
static int maxLength(String s, int n)
{
// As it's subsequence - assuming first
// open brace would map to a first close
// brace which occurs after the open brace
// to make subsequence balanced and second
// open brace would map to second close
// brace and so on.
// Variable to count all the open brace
// that does not have the corresponding
// closing brace.
int invalidOpenBraces = 0;
// To count all the close brace that
// does not have the corresponding open brace.
int invalidCloseBraces = 0;
// Iterating over the String
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') {
// Number of open braces that
// hasn't been closed yet.vvvvvv
invalidOpenBraces++;
}
else {
if (invalidOpenBraces == 0) {
// Number of close braces that
// cannot be mapped to any open
// brace.
invalidCloseBraces++;
}
else {
// Mapping the ith close brace
// to one of the open brace.
invalidOpenBraces--;
}
}
}
return (
n - (invalidOpenBraces
+ invalidCloseBraces));
}
// Driver Code
public static void main(String[] args)
{
String s = "()(((((()";
int n = s.length();
System.out.println(maxLength(s, n));
}
}
Python3
# Python3 program to find length of
# the longest balanced subsequence
def maxLength(s, n):
# As it's subsequence - assuming first
# open brace would map to a first close
# brace which occurs after the open brace
# to make subsequence balanced and second
# open brace would map to second close
# brace and so on.
# Variable to count all the open brace
# that does not have the corresponding
# closing brace.
invalidOpenBraces = 0;
# To count all the close brace that does
# not have the corresponding open brace.
invalidCloseBraces = 0;
# Iterating over the String
for i in range(n):
if( s[i] == '(' ):
# Number of open braces that
# hasn't been closed yet.
invalidOpenBraces += 1
else:
if(invalidOpenBraces == 0):
# Number of close braces that
# cannot be mapped to any open
# brace.
invalidCloseBraces += 1
else:
# Mapping the ith close brace
# to one of the open brace.
invalidOpenBraces -= 1
return (
n - (
invalidOpenBraces + invalidCloseBraces))
# Driver Code
s = "()(((((()"
n = len(s)
print(maxLength(s, n))
C#
// C# program to find length of the
// longest balanced subsequence.
using System;
class GFG {
static int maxLength(String s, int n)
{
// As it's subsequence - assuming first
// open brace would map to a first close
// brace which occurs after the open brace
// to make subsequence balanced and second
// open brace would map to second close
// brace and so on.
// Variable to count all the open brace
// that does not have the corresponding
// closing brace.
int invalidOpenBraces = 0;
// To count all the close brace that
// does not have the corresponding open brace.
int invalidCloseBraces = 0;
// Iterating over the String
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
// Number of open braces that
// hasn't been closed yet.
invalidOpenBraces++;
}
else {
if (invalidOpenBraces == 0) {
// Number of close braces that
// cannot be mapped to any open brace.
invalidCloseBraces++;
}
else {
// Mapping the ith close brace to
// one of the open brace.
invalidOpenBraces--;
}
}
}
return (
n - (invalidOpenBraces
+ invalidCloseBraces));
}
// Driver Code
public static void Main()
{
string s = "()(((((()";
int n = s.Length;
Console.WriteLine(maxLength(s, n));
}
}
Javascript
<script>
// Javascript program to find the length of the
// longest balanced subsequence.
function maxLength(s, n)
{
// As it's subsequence - assuming first
// open brace would map to a first close
// brace which occurs after the open brace
// to make subsequence balanced and second
// open brace would map to second close
// brace and so on.
// Variable to count all the open brace
// that does not have the corresponding
// closing brace.
let invalidOpenBraces = 0;
// To count all the close brace that
// does not have the corresponding open brace.
let invalidCloseBraces = 0;
// Iterating over the String
for (let i = 0; i < n; i++) {
if (s[i] == '(') {
// Number of open braces that
// hasn't been closed yet.vvvvvv
invalidOpenBraces++;
}
else {
if (invalidOpenBraces == 0) {
// Number of close braces that
// cannot be mapped to any open
// brace.
invalidCloseBraces++;
}
else {
// Mapping the ith close brace
// to one of the open brace.
invalidOpenBraces--;
}
}
}
return (
n - (invalidOpenBraces
+ invalidCloseBraces));
}
// driver program
let s = "()(((((()";
let n = s.length;
document.write(maxLength(s, n));
</script>
Producción:
4
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA