fork download
copy 
  1. def reducir_cadena(cadena):
  2.     """Reduce una cadena de caracteres según las reglas del problema.
  3.  
  4.     Args:
  5.         cadena: La cadena de caracteres a reducir.
  6.  
  7.     Returns:
  8.         La longitud mínima de la cadena reducida.
  9.     """
  10.     # Validación de longitud de cadena
  11.     if len(cadena) > 5 * 1000:
  12.         raise ValueError("La longitud de la cadena no debe exceder 5000 caracteres.")
  13.  
  14.     pila = []
  15.  
  16.     for c in cadena:
  17.         if c == '(':
  18.             pila.append(c)  # Agregar '(' a la pila
  19.         elif c == ')':
  20.             # Si hay un '(' en la pila, lo eliminamos
  21.             if pila and pila[-1] == '(':
  22.                 pila.pop()  # Eliminamos el par de ()
  23.             else:
  24.                 pila.append(c)  # Agregamos ')' si no se puede eliminar
  25.         elif c == '?':
  26.             # Al encontrar un '?', tratamos de usarlo para balancear
  27.             if pila and (pila[-1] == '(' or pila[-1] == '?'):
  28.                 # Usar '?' para eliminar '(' o para eliminar otro '?'
  29.                 pila.pop()  # Eliminar un '(' o un '?' balanceado
  30.             else:
  31.                 # Usamos '?' como un '('
  32.                 pila.append('(')
  33.  
  34.     # Al final, la longitud de la pila representa los caracteres no eliminados.
  35.     return len(pila)
  36.  
  37. # Ejemplo de uso:
  38. cadena = "??"
  39. resultado = reducir_cadena(cadena)
  40. print("Longitud mínima:", resultado)  # Imprimirá: Longitud mínima: 0
  41.  
  42. cadena = "())?"
  43. resultado = reducir_cadena(cadena)
  44. print("Longitud mínima:", resultado)  # Imprimirá: Longitud mínima: 2
  45.  
  46. # Prueba con una cadena larga (sin exceder el límite)
  47. cadena_larga = "("*1000 + "?"*1000 + ")"*1000
  48. resultado_largo = reducir_cadena(cadena_larga)
  49. print("Longitud mínima para cadena larga:", resultado_largo)  # Resultado variable según la cadena
  50.  
  51. # Prueba con una cadena que excede el límite
  52. try:
  53.     cadena_excedida = "?" * 5001  # Más de 5000 caracteres
  54.     reducir_cadena(cadena_excedida)
  55. except ValueError as e:
  56.     print(e)  # Imprimirá: La longitud de la cadena no debe exceder 5000 caracteres.
  57.  
  58. # Complejidad algorítmica: O(n)
  59.  
Success #stdin #stdout 0.04s 65424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
('Longitud m\xc3\xadnima:', 0)
('Longitud m\xc3\xadnima:', 2)
('Longitud m\xc3\xadnima para cadena larga:', 1000)
La longitud de la cadena no debe exceder 5000 caracteres.
https://ideone.com/SIhVo4
language:
Python (PyPy 2.7.13)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!