¿Cómo puede encontrar todos los parens no balanceados en una cadena en tiempo lineal con memoria constante?

Me dieron el siguiente problema durante una entrevista:

Da una cadena que contiene alguna mezcla de parens (no corchetes o llaves, solo parens) con otros caracteres alfanuméricos, identifica a todos los parens que no tienen pares coincidentes.

Por ejemplo, en la cadena ") (ab))", los índices 0 y 5 contienen parens que no tienen pares coincidentes.

Presento una solución O (n) que funciona usando la memoria O (n), usando una pila y revisando la cadena una vez que agrego parens a la pila y los quito de la pila cada vez que me encuentro con un par de cierre y la parte superior de la pila contenía Un par de apertura.

Posteriormente, el entrevistador señaló que el problema podría resolverse en tiempo lineal con memoria constante (como en, sin uso de memoria adicional además de lo que ocupa la entrada).

Le pregunté cómo y ella dijo algo acerca de pasar por la cadena una vez desde la izquierda para identificar a todos los padres abiertos, y luego una segunda vez desde la derecha para identificar a todos los padres cercanos ... o tal vez fue al revés. Realmente no entendí y no quería pedirle que me agarrara de la mano.

¿Alguien puede aclarar la solución que sugirió?

$O(1)$$\Theta(\log(n))$$n$

Puede mantener el principio básico del algoritmo que utilizó. Perdiste la oportunidad de optimizar la memoria.

usando una pila y yendo a través de la cadena una vez agregando parens a la pila y eliminándolos de la pila cada vez que me encuentro con un par de cierre y la parte superior de la pila contenía un par de apertura

Entonces, ¿qué contiene esta pila? Nunca va a contener ()(un paréntesis de apertura seguido de un paréntesis de cierre), ya que cada vez que )aparece aparece el pop en (lugar de presionar el ). Por lo tanto, la pila siempre tiene la forma )…)(…(: un par de paréntesis de cierre seguidos de un par de paréntesis de apertura.

No necesitas una pila para representar esto. Solo recuerde el número de paréntesis de cierre y el número de paréntesis de apertura.

Si procesa la cadena de izquierda a derecha, utilizando estos dos contadores, lo que tiene al final es el número de paréntesis de cierre no coincidentes y el número de paréntesis de apertura no coincidentes.

$\Theta(n)$

En resumen: procese la cadena de izquierda a derecha. Mantenga un contador de paréntesis de apertura sin igual. Si ve un paréntesis de apertura, incremente el contador. Si ve un paréntesis de cierre y el contador no es cero, disminuya el contador. Si ve un paréntesis de cierre y el contador es cero, muestre el índice actual como un paréntesis de cierre no coincidente.

El valor final del contador es el número de paréntesis de apertura no coincidentes, pero esto no le da su posición. Tenga en cuenta que el problema es simétrico. Para enumerar las posiciones de paréntesis de apertura no coincidentes, simplemente ejecute el algoritmo en la dirección opuesta.

Ejercicio 1: escriba esto en una notación formal (matemáticas, pseudocódigo o su lenguaje de programación favorito).

Ejercicio 2: convénzase usted mismo de que este es el mismo algoritmo que Apass.Jack , solo que se explica de manera diferente.

Como podemos ignorar todos los caracteres alfanuméricos, asumiremos que la cadena contiene solo paréntesis de ahora en adelante. Como en la pregunta, solo hay un tipo de paréntesis, "()".

Si seguimos eliminando paréntesis equilibrados hasta que no se puedan eliminar más paréntesis equilibrados, todos los paréntesis restantes deben verse como ")) ...) ((... (", que son paréntesis desequilibrados. Esta observación sugiere que deberíamos encontrar primero ese punto de inflexión) , antes de lo cual solo tenemos paréntesis de cierre desequilibrados y después de lo cual solo tenemos paréntesis de apertura desequilibrados.

Aquí está el algoritmo. En pocas palabras, calcula primero el punto de inflexión. Luego genera un paréntesis de cierre adicional, escaneando la cadena desde el inicio hacia la derecha hasta el punto de inflexión. Simétricamente, genera paréntesis de apertura adicionales, escaneando desde el extremo hacia la izquierda hasta el punto de inflexión.

str$n$

Initialize turning_point=0, maximum_count=0, count=0. Para cada uno ide 0a n-1hacer lo siguiente.

1. Si str[i] = ')', agregue 1 a count; de lo contrario, reste 1.
2. Si count > maximum_count, establecer turning_point=iy maximum_count=count.

Ahora turning_pointes el índice del punto de inflexión.

Restablecer maximum_count=0, count=0. Para cada uno ide 0a turning_pointhacer lo siguiente.

1. Si str[i] = ')', agregue 1 a count; de lo contrario, reste 1.
2. Si count > maximum_count, listo maximum_count = count. Salida icomo el índice de un paréntesis de cierre desequilibrado.

Restablecer maximum_count=0, count=0. Para cada uno ide n-1hacia turning_point+1abajo, haga lo siguiente.

1. Si str[j] = '(', agregue 1 a count; de lo contrario, reste 1.
2. Si count > maximum_count, listo maximum_count = count. Salida icomo el índice de un paréntesis de apertura desequilibrado.

$O(n)$$O(1)$$O(u)$$u$

Si analizamos el algoritmo anterior, veremos que, de hecho, no necesitamos encontrar y usar el punto de inflexión en absoluto. La agradable observación de que todos los paréntesis de cierre desequilibrados ocurren antes de que todos los paréntesis de apertura desequilibrados puedan ignorarse aunque sean interesantes.

Aquí hay código en Python .

Simplemente presione "ejecutar" para ver varios resultados de la prueba.

Ejercicio 1. Demuestre que el algoritmo anterior generará un conjunto de paréntesis con la menor cardinalidad, de modo que los paréntesis restantes estén equilibrados.

Problema 1. ¿Podemos generalizar el algoritmo al caso cuando la cadena contiene dos tipos de paréntesis como "() []"? Tenemos que determinar cómo reconocer y tratar la nueva situación, el caso de intercalación, "([)]".