Algoritmo 1: Pila

La solución utiliza una pila para rastrear paréntesis no emparejados y sus posiciones. Al encontarr un paréntesis de cierre que coincide con el tope de la pila, se extrae el elemento y se calcula la longitud de la subcadena válida. Si la pila queda vacía tras la extracción, la subcadena abarca desde el inicio; de lo contrario, comienza después de la posición actual del tope.

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

bool esParCompatible(char abierto, char cerrado) {
    if (abierto == '(' && cerrado == ')') return true;
    if (abierto == '[' && cerrado == ']') return true;
    if (abierto == '{' && cerrado == '}') return true;
    return false;
}

int main() {
    string secuencia;
    cin >> secuencia;
    stack<pair<char, int>> pila;
    int maxLongitud = 0;

    for (int idx = 0; idx < secuencia.size(); idx++) {
        if (!pila.empty() && esParCompatible(pila.top().first, secuencia[idx])) {
            pila.pop();
            if (pila.empty()) {
                maxLongitud = max(maxLongitud, idx + 1);
            } else {
                maxLongitud = max(maxLongitud, idx - pila.top().second);
            }
        } else {
            pila.push({secuencia[idx], idx});
        }
    }
    cout << maxLongitud << endl;
    return 0;
}

Algoritmo 2: Programación Dinámica

Se define dp[i] como la longitud de la subcadena válida más larga que termina en la posición i. Para un paréntesis de cierre en i, se verifica si el carácter en la posición j = i - dp[i-1] - 1 es un paréntesis de apertura coincidente. Si hay coincidencia, se actauliza dp[i] sumando la longitud del par actual (dp[i-1] + 2) y cualquier subcadena válida adyacente anterior (dp[j-1]).

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int TAM_MAX = 100010;
int dp[TAM_MAX];

bool esParValido(char abierto, char cerrado) {
    if (abierto == '(' && cerrado == ')') return true;
    if (abierto == '[' && cerrado == ']') return true;
    if (abierto == '{' && cerrado == '}') return true;
    return false;
}

int main() {
    string entrada;
    cin >> entrada;
    int n = entrada.size();
    int resultado = 0;

    for (int i = 1; i < n; i++) {
        if (entrada[i] == '(' || entrada[i] == '[' || entrada[i] == '{') continue;
        
        int posAnterior = i - dp[i-1] - 1;
        if (posAnterior >= 0 && esParValido(entrada[posAnterior], entrada[i])) {
            dp[i] = dp[i-1] + 2;
            if (posAnterior - 1 >= 0) {
                dp[i] += dp[posAnterior - 1];
            }
            resultado = max(resultado, dp[i]);
        }
    }
    cout << resultado << endl;
    return 0;
}