Longest Valid Parentheses

Q: ¿Existe una solución de programación dinámica para el problema de los paréntesis válidos más largos?

Sí. Sea end[i] la longitud de la subcadena bien formada más larga que termina en el índice i ; es 0 cuando s[i] es ( . Si s[i-1] es ( , entonces end[i] = end[i-2] + 2 . Si es ) , mira j = i - end[i-1] - 1 , el carácter anterior a la secuencia que termina en i-1 : cuando s[j] es ( , este envuelve esa secuencia, y end[i] = end[i-1] + 2 + end[j-1] , donde el último término se une a una secuencia que lo toca por la izquierda. La respuesta es el mayor end[i] , en tiempo y memoria O(n) .

DifícilPila Programación dinámica

+10

Recibes una cadena s formada únicamente por los caracteres ( y ). Encuentra la subcadena más larga (una secuencia de caracteres consecutivos) que esté bien formada: cada ( en ella se cierra con un ) posterior también en ella, y los pares están anidados correctamente, como en (()()). Devuelve la longitud de esa subcadena, o 0 si ni siquiera aparece ().

Función

longestValidParentheses(s: string) → integer

sstring: una cadena de caracteres ( y )
Devuelveinteger: la longitud de la subcadena bien formada más larga, o 0 si no hay ninguna

Restricciones

1 ≤ s.length ≤ 6 × 10⁴
Cada carácter de s es ( o ).

Ejemplos

Entrada: s = "()(())"
Salida: 6
Explicación: La cadena completa está bien formada: () seguida de (()). Dos partes bien formadas una al lado de la otra forman una sola parte bien formada, así que la respuesta son los 6 caracteres.

Entrada: s = "())((())"
Salida: 4
Explicación: El ) en el índice 2 no tiene pareja, así que ninguna solución puede cruzarlo, y el ( en el índice 3 nunca se cierra. La secuencia más larga es (()) desde el índice 4 hasta el 7, con una longitud de 4, que supera a () al principio.

Entrada: s = "))(("
Salida: 0
Explicación: Ambos ) aparecen antes que ambos (, así que ningún ( se cierra. Ninguna subcadena está bien formada y la respuesta es 0.

+21 pruebas ocultas al enviar

Para ir más allá

¿También puedes indicar dónde empieza la subcadena bien formada más larga, eligiendo la que aparece más a la izquierda cuando varias tienen la misma longitud?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Dos cosas hacen que esto sea más difícil que revisar una sola cadena. Las partes bien formadas se unen cuando se tocan, así que () y (()) una junto a la otra cuentan como una sola secuencia de 6. Y un carácter suelto, como el ) en ())(()), corta la cadena, de modo que ninguna solución puede atravesarlo. Probar cada inicio cuesta O(n²). La solución es recordar dónde comenzó la secuencia actual: una pila de índices con un marcador base en el fondo lo hace en una sola pasada, y dos pasadas con contadores simples lo hacen sin usar ninguna pila.

Construye una subcadena desde cada posición inicial

Correcto, pero no termina con las pruebas más grandes

Intuición

Lee una subcadena de izquierda a derecha con un balance que suma 1 por cada ( y resta 1 por cada ). La subcadena está bien formada exactamente cuando el balance nunca baja de 0 y termina en 0. Estar por debajo de 0 significa que llegó un ) sin que hubiera nada abierto que cerrar.

Así que fija un inicio y avanza hacia la derecha, actualizando el balance carácter por carácter. Cada vez que vuelve a 0, el tramo desde el inicio hasta aquí está bien formado, y registras su longitud. En cuanto baja de 0, detente: ese ) queda sin emparejar en todos los tramos más largos que comienzan en este inicio. Toda subcadena bien formada tiene algún inicio, y pruebas todos sus posibles finales, así que no se omite ninguna.

El costo es el problema. En una cadena de 59998 ( seguida de (), el balance nunca baja de 0, así que cada inicio avanza hasta el final: aproximadamente n²/2 = 1.8 × 10^9 pasos para n = 6 × 10^4. Las pruebas grandes están construidas así. (Comprobar cada subcadena desde cero en vez de ampliarla sería aún peor, O(n³).)

Algoritmo

Asigna 0 a best.
Para cada inicio, asigna 0 a balance y recorre el final desde el inicio hasta el último carácter.
Suma 1 por ( y resta 1 por ).
Si balance es menor que 0, detén este inicio. Si es 0, actualiza best con la longitud del tramo end - start + 1.
Devuelve best.

def longestValidParentheses(s):
    best = 0
    for start in range(len(s)):
        balance = 0
        for end in range(start, len(s)):
            balance += 1 if s[end] == "(" else -1
            if balance < 0:
                # A ')' without a partner: no longer run starts here
                break
            if balance == 0:
                best = max(best, end - start + 1)
    return best

Pila de índices con un marcador de base

Intuición

Emparejar paréntesis con una pila es algo conocido: inserta cada ( y extrae uno por cada ). Aquí también necesitas longitudes, así que inserta índices y mantén un índice adicional en la parte inferior de la pila: la base, la posición justo antes de la secuencia en la que estás. Al principio no se ha leído nada, así que la base es -1.

Con (, inserta su índice. Con ), extrae un elemento. Pueden ocurrir dos cosas. Si la pila queda vacía, extrajiste la base, así que este ) no tenía nada que cerrar. Ninguna subcadena bien formada puede contenerlo, y se convierte en la nueva base: inserta su índice. De lo contrario, el índice que queda arriba es el último carácter antes de la secuencia que termina en i: ya sea un ( que sigue abierto o la base. Todo lo que queda después de este índice hasta i está emparejado, y la secuencia no puede extenderse más hacia la izquierda, así que su longitud es i - top.

Este es el caso de ())((()):

i = 0, (: inserta 0. Pila [-1, 0].
i = 1, ): extrae 0. La cima es -1, así que la secuencia mide 1 - (-1) = 2.
i = 2, ): extrae -1 y la pila queda vacía. Este ) no tiene pareja, así que inserta 2 como nueva base. Pila [2].
i = 3, 4, 5, tres (: insértalos. Pila [2, 3, 4, 5].
i = 6, ): extrae 5. La cima es 4, así que la secuencia mide 6 - 4 = 2.
i = 7, ): extrae 4. La cima es 3, así que la secuencia mide 7 - 3 = 4, la respuesta.

La base es lo que permite unir las partes contiguas. En ()(()), el primer par mide 1 - (-1) = 2, y el último ) extrae el índice 2 y vuelve a encontrar -1 en la cima, así que mide 5 - (-1) = 6. Medir desde el ( correspondiente daría 4 y dejaría fuera el () de delante. Cada índice se inserta y se extrae como máximo una vez, así que el recorrido es O(n), y la pila puede contener hasta n+1 índices.

Algoritmo

Inicia una pila que contenga -1 y establece best en 0.
Para cada índice i, inserta i si s[i] es (.
Si es ), extrae un elemento.
Si la pila está vacía ahora, inserta i como nueva base. De lo contrario, actualiza best con i - top.
Devuelve best.

def longestValidParentheses(s):
    # The bottom of the stack is the index just before the current run
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # This ')' has no partner: it becomes the new base
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

Cuenta las aperturas y los cierres en dos pasadas

Intuición

La pila solo te indica dónde empezó la secuencia actual. Dos contadores también pueden hacerlo. Recorre de izquierda a derecha contando opens y closes desde el último reinicio. Cuando son iguales, todo lo que hay desde el reinicio está bien formado, con una longitud de 2 × closes. Cuando closes se adelanta, un ) no tiene pareja, justo cuando la pila perdió su base, así que reinicia ambos contadores a 0.

Un recorrido no basta. Un ( que nunca se cierra mantiene opens por delante para siempre, y los recuentos nunca vuelven a coincidir. En ((), el recorrido de izquierda a derecha termina con 2 aperturas y 1 cierre, y no informa nada, aunque () está justo ahí. Así que recorre la cadena una segunda vez, de derecha a izquierda, intercambiando los papeles: reinicia cuando opens se adelanta. Al leer hacia atrás, (() da un cierre, luego una apertura (iguales: longitud 2), y después una apertura que reinicia los contadores. La respuesta es el mayor de los resultados de los dos recorridos.

Por qué dos recorridos detectan todas las secuencias: la secuencia más larga está delimitada por caracteres que nunca pueden emparejarse, o por los extremos de la cadena. Si su límite izquierdo es un ) suelto o el principio, el recorrido de izquierda a derecha se reinicia justo donde empieza la secuencia y ve que los recuentos coinciden donde termina. Si su límite izquierdo es un ( suelto, el límite derecho no puede ser un ), porque ese ) cerraría el ( suelto y la secuencia sería más larga. Así que el límite derecho es un ( suelto o el final, y el recorrido de derecha a izquierda detecta la secuencia de la misma manera. Cada recorrido lee la cadena una vez usando dos enteros, así que el tiempo es O(n) y la memoria adicional, O(1).

Algoritmo

Establece best en 0, y opens y closes en 0.
Recorre de izquierda a derecha, contando cada carácter. Cuando los conteos sean iguales, actualiza best con 2 × closes. Cuando closes sea mayor, restablece ambos a 0.
Restablece ambos contadores y luego recorre de derecha a izquierda de la misma manera, excepto que restableces cuando opens sea mayor.
Devuelve best.

def longestValidParentheses(s):
    best = 0

    # Left to right: more ')' than '(' ends every run that started earlier
    opens = closes = 0
    for ch in s:
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * closes)
        elif closes > opens:
            opens = closes = 0

    # Right to left: catches the runs that an unmatched '(' hid from the first pass
    opens = closes = 0
    for ch in reversed(s):
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * opens)
        elif opens > closes:
            opens = closes = 0

    return best

Errores comunes y casos límite

La mayoría de las respuestas incorrectas cuentan los pares correctos en los lugares equivocados o pierden el inicio de una secuencia.

Contar los pares coincidentes en toda la cadena. ())((()) tiene 3 pares, pero no están todos juntos, y la respuesta es 4, no 6.
Medir una secuencia desde el ( coincidente. En ()(()), el último ) coincide con el índice 2, lo que da 4 y omite el () que está delante. Mide desde el índice que queda en la pila después de extraer el elemento.
Empezar con una pila vacía. Entonces, el primer ) de ()) no tiene nada con qué compararse, y un ) sin pareja extrae un elemento de una pila vacía. La base -1 soluciona ambos problemas.
Ejecutar los contadores en una sola dirección. (() devuelve 0 de izquierda a derecha, y ()) devuelve 0 de derecha a izquierda; la respuesta es 2 para ambos.
Restablecer los contadores cuando son iguales. Que los recuentos sean iguales significa que la secuencia aún puede crecer, como en ()(); restablécelos solo cuando un lado se adelanta.
En Lua y R las posiciones empiezan en 1, así que la primera base es 0, no -1.

Preguntas frecuentes4

¿Cuál es la complejidad temporal del problema de los paréntesis válidos más largos?

Tanto la solución con pila como la solución con contadores de dos pasadas leen cada carácter un número constante de veces, por lo que se ejecutan en tiempo O(n). La pila necesita O(n) de memoria en el peor de los casos, como ocurre con una cadena formada únicamente por (, mientras que los contadores necesitan O(1). Probar cada inicio es O(n²).

¿Por qué la pila empieza en -1?

La longitud de la secuencia es el índice actual menos el índice justo antes de la secuencia. Para una secuencia que empieza en el índice 0, ese índice anterior es -1, un paso antes de la cadena. Insertar -1 primero significa que la pila nunca está vacía cuando un ) emparejado mide, y cuando un ) sin pareja lo extrae, ese ) pasa a ser la nueva base.

¿Existe una solución de programación dinámica para el problema de los paréntesis válidos más largos?

Sí. Sea end[i] la longitud de la subcadena bien formada más larga que termina en el índice i; es 0 cuando s[i] es (. Si s[i-1] es (, entonces end[i] = end[i-2] + 2. Si es ), mira j = i - end[i-1] - 1, el carácter anterior a la secuencia que termina en i-1: cuando s[j] es (, este envuelve esa secuencia, y end[i] = end[i-1] + 2 + end[j-1], donde el último término se une a una secuencia que lo toca por la izquierda. La respuesta es el mayor end[i], en tiempo y memoria O(n).

¿Por qué no basta con una sola pasada con contadores?

Un recorrido de izquierda a derecha solo se reinicia cuando ) supera en número a (. Un ( adicional que nunca se cierra mantiene separados los conteos durante el resto de la cadena, así que el recorrido nunca los ve coincidir. En ((), termina con 2 paréntesis de apertura y 1 de cierre, y no encuentra nada. Leer de derecha a izquierda trata el ( suelto del mismo modo que el primer recorrido trata un ) suelto, así que los dos recorridos juntos abarcan todas las secuencias.

Python

def longestValidParentheses(s):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "()(())"

Esperado

Longest Valid Parentheses

Función

Restricciones

Ejemplos

Pistas

Solución

Construye una subcadena desde cada posición inicial

Pila de índices con un marcador de base

Cuenta las aperturas y los cierres en dos pasadas

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares