Eliminar pares adyacentes
La misión
Problema
Dado un texto, elimina repetidamente cualquier par de caracteres vecinos que sean idénticos. Eliminar un par junta los caracteres de alrededor, lo que puede crear un nuevo par vecino para eliminar. Sigue hasta que no quede ningún par así y devuelve lo que queda.
Ejemplos
Input: text = "abbaca"
Output: "ca"
Por qué: quitar bb deja aaca, y quitar aa deja ca
Input: text = "azxxzy"
Output: "ay"
Por qué: eliminar xx crea zz, que después también se elimina
Input: text = "aa"
Output: ""
Por qué: caso límite: todo se cancela y no queda nada
Pistas
0 / 3
Volver a recorrer todo el texto después de cada eliminación es correcto, pero lento. Fíjate en que una eliminación solo puede afectar a los caracteres que rodean inmediatamente el hueco.
Construye el resultado de izquierda a derecha y mira siempre su último carácter. Una estructura cuyas únicas operaciones baratas son agregar al final y quitar del final encaja exactamente con esto.
Haz push de los caracteres en una pila, uno por uno. Antes de cada push, compara el carácter entrante con el del tope: si coinciden, haz pop en lugar de push, lo que realiza la cancelación y deja expuesto de inmediato al siguiente candidato de abajo. Al final, une lo que quedó en la pila.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Solución
Una pila (stack) guarda la parte de la respuesta construida hasta ahora, y su tope siempre es el carácter junto al que quedaría un recién llegado. Por eso una coincidencia se cancela haciendo pop en lugar de push, lo que además deja expuesto el carácter de abajo como nuevo vecino; así, las cancelaciones encadenadas ocurren solas, sin volver a recorrer nada. Cada carácter entra y sale de la pila como máximo una vez. El tiempo es O(n) y el espacio es O(n) por la pila.
def collapse_pairs(text):
stack = []
for ch in text:
if stack and stack[-1] == ch:
stack.pop() # the pair annihilates, exposing the one below
else:
stack.append(ch)
return "".join(stack)
print(collapse_pairs("abbaca")) # -> ca
print(collapse_pairs("azxxzy")) # -> ay
print(collapse_pairs("aa")) # ->¿Lo que te frena es la idea y no el código? Paréntesis válidos lo explica.