Dada una secuencia de paréntesis de longitud uniforme. La tarea es encontrar cuántas maneras hay de hacer subsecuencias de paréntesis equilibradas a partir de la secuencia dada de longitud 2 y 4. La secuencia() es una secuencia de paréntesis de longitud 2. Una subsecuencia es una secuencia que se puede derivar de otra secuencia mediante eliminando algunos o ningún elemento sin cambiar el orden de los elementos restantes.
Nota: «1» representa el paréntesis de apertura y «2» representa el paréntesis de cierre.
Ejemplos:
Input: 1 2 1 1 2 2 Output: 14 Input: 1 2 1 2 Output: 4
Enfoque: para la subsecuencia de longitud 2 , solo veremos para cada 1 cuántos 2 hay, lo que se puede lograr fácilmente tomando una simple suma de sufijos del número de 2 presentes en la secuencia. Entonces, primero tome la suma del sufijo del número de 2 presentes en la secuencia.
Para una subsecuencia de longitud 4 hay 2 opciones:
El primero es 1 1 2 2
y el otro es 1 2 1 2.
Para el primero, ejecute un ciclo de izquierda a derecha para obtener el primer paréntesis abierto un ciclo interno para obtener el siguiente paréntesis de apertura ahora de la array de sufijos podemos obtener la cuenta de 2 después del segundo paréntesis de apertura y calcular el número de subsecuencia por conteo*(conteo-1)/2 porque para cada paréntesis de cierre para el paréntesis de apertura interior obtenemos un número de opciones de conteo-1 para el primer paréntesis de apertura.
Para el segundo tipo de subsecuencia, nuevamente ejecutamos un ciclo de izquierda a derecha para obtener el primer corchete abierto y un ciclo interno para obtener el siguiente corchete de apertura. Luego calculamos el número de subsecuencias obteniendo el conteo de 2 después del primer paréntesis de apertura simplemente restando el conteo de 2 después del segundo paréntesis de apertura y el conteo de 2 después del primer paréntesis de apertura y multiplicándolo por el conteo de 2 después del Segundo paréntesis de apertura (obtenemos todos estos valores de la array de sufijos de frecuencia).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
void countWays(int a[], int n)
{
int i, j;
long suff[n];
if (a[n - 1] == 2)
suff[n - 1] = 1;
// Taking the frequency suffix sum of the
// number of 2's present after every index
for (i = n - 2; i >= 0; i--)
{
if (a[i] == 2)
suff[i] = suff[i + 1] + 1;
else
suff[i] = suff[i + 1];
}
// Storing the count of subsequence
long ss = 0;
// Subsequence of length 2
for (i = 0; i < n; i++)
{
if (a[i] == 1)
ss += suff[i];
}
// Subsequence of length 4 of type 1 1 2 2
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (a[i] == 1 && a[j] == 1 && suff[j] >= 2)
{
ss += (suff[j]) * (suff[j] - 1) / 2;
}
}
}
// Subsequence of length 4 of type 1 2 1 2
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (a[i] == 1 && a[j] == 1
&& (suff[i] - suff[j]) >= 1
&& suff[j] >= 1)
{
ss += (suff[i] - suff[j]) * suff[j];
}
}
}
cout << (ss);
}
// Driver code
int main()
{
int a[] = { 1, 2, 1, 1, 2, 2 };
int n = 6;
countWays(a, n);
return 0;
}
// This code is contributed by Rajput-Ji
Java
// Java implementation of above approach
class GFG {
public static void countWays(int a[], int n)
{
int i, j;
long suff[] = new long[n];
if (a[n - 1] == 2)
suff[n - 1] = 1;
// Taking the frequency suffix sum of the
// number of 2's present after every index
for (i = n - 2; i >= 0; i--)
{
if (a[i] == 2)
suff[i] = suff[i + 1] + 1;
else
suff[i] = suff[i + 1];
}
// Storing the count of subsequence
long ss = 0;
// Subsequence of length 2
for (i = 0; i < n; i++)
{
if (a[i] == 1)
ss += suff[i];
}
// Subsequence of length 4 of type 1 1 2 2
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (a[i] == 1 && a[j] == 1
&& suff[j] >= 2)
{
ss += (suff[j]) * (suff[j] - 1) / 2;
}
}
}
// Subsequence of length 4 of type 1 2 1 2
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (a[i] == 1 && a[j] == 1
&& (suff[i] - suff[j]) >= 1
&& suff[j] >= 1)
{
ss += (suff[i] - suff[j]) * suff[j];
}
}
}
System.out.println(ss);
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 2, 1, 1, 2, 2 };
int n = 6;
countWays(a, n);
}
}
Python 3
# Python 3 implementation of # above approach def countWays(a, n): suff = [0] * n if (a[n - 1] == 2): suff[n - 1] = 1 # Taking the frequency suffix sum # of the number of 2's present # after every index for i in range(n - 2, -1, -1): if (a[i] == 2): suff[i] = suff[i + 1] + 1 else: suff[i] = suff[i + 1] # Storing the count of subsequence ss = 0 # Subsequence of length 2 for i in range(n): if (a[i] == 1): ss += suff[i] # Subsequence of length 4 of type 1 1 2 2 for i in range(n): for j in range(i + 1, n): if (a[i] == 1 and a[j] == 1 and suff[j] >= 2): ss += (suff[j]) * (suff[j] - 1) // 2 # Subsequence of length 4 # of type 1 2 1 2 for i in range(n): for j in range(i + 1, n): if (a[i] == 1 and a[j] == 1 and (suff[i] - suff[j]) >= 1 and suff[j] >= 1): ss += (suff[i] - suff[j]) * suff[j] print(ss) # Driver Code if __name__ == "__main__": a = [1, 2, 1, 1, 2, 2] n = 6 countWays(a, n) # This code is contributed # by ChitraNayal
C#
// C# implementation of
// above approach
using System;
class GFG
{
public static void countWays(int[] a, int n)
{
int i, j;
long[] suff = new long[n];
if (a[n - 1] == 2)
suff[n - 1] = 1;
// Taking the frequency suffix
// sum of the number of 2's
// present after every index
for (i = n - 2; i >= 0; i--)
{
if (a[i] == 2)
suff[i] = suff[i + 1] + 1;
else
suff[i] = suff[i + 1];
}
// Storing the count of subsequence
long ss = 0;
// Subsequence of length 2
for (i = 0; i < n; i++)
{
if (a[i] == 1)
ss += suff[i];
}
// Subsequence of length 4
// of type 1 1 2 2
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (a[i] == 1 && a[j] == 1
&& suff[j] >= 2) {
ss += (suff[j]) * (suff[j] - 1) / 2;
}
}
}
// Subsequence of length 4
// of type 1 2 1 2
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (a[i] == 1 && a[j] == 1
&& (suff[i] - suff[j]) >= 1
&& suff[j] >= 1) {
ss += (suff[i] - suff[j]) * suff[j];
}
}
}
Console.WriteLine(ss);
}
// Driver Code
public static void Main()
{
int[] a = { 1, 2, 1, 1, 2, 2 };
int n = 6;
countWays(a, n);
}
}
// This code is contributed by Shashank
Javascript
<script>
// Javascript implementation of above approach
function countWays(a, n)
{
let i, j;
let suff = new Array(n);
if (a[n - 1] == 2)
suff[n - 1] = 1;
// Taking the frequency suffix sum of the
// number of 2's present after every index
for (i = n - 2; i >= 0; i--)
{
if (a[i] == 2)
suff[i] = suff[i + 1] + 1;
else
suff[i] = suff[i + 1];
}
// Storing the count of subsequence
let ss = 0;
// Subsequence of length 2
for (i = 0; i < n; i++)
{
if (a[i] == 1)
ss += suff[i];
}
// Subsequence of length 4 of type 1 1 2 2
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (a[i] == 1 && a[j] == 1 && suff[j] >= 2)
{
ss += (suff[j]) * (suff[j] - 1) / 2;
}
}
}
// Subsequence of length 4 of type 1 2 1 2
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (a[i] == 1 && a[j] == 1
&& (suff[i] - suff[j]) >= 1
&& suff[j] >= 1)
{
ss += (suff[i] - suff[j]) * suff[j];
}
}
}
document.write(ss);
}
let a = [ 1, 2, 1, 1, 2, 2 ];
let n = 6;
countWays(a, n);
// This code is contributed by divyeshrabadiya07.
</script>
14
Complejidad de tiempo: O(N*N) // N es la longitud de la array
Espacio auxiliar: O(N) // Se utiliza una array adicional de tamaño N