Codificación, inversión y palíndromos de strings
Implemente la inversión de palabras in-place, la codificación por longitud de secuencias y la detección de palíndromos, incluida la técnica de expansión alrededor del centro.
Codificación, inversión y palíndromos de strings es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Invertir una cadena in situ
Las cadenas de Python son inmutables, por lo que invertirlas «in situ» significa convertirlas en una lista de caracteres, intercambiar elementos con dos punteros y volver a unirlos. El intercambio clásico con dos punteros consiste en colocar left en el índice 0 y right en el último índice; intercambie los caracteres y acerque los punteros hacia el centro hasta que se crucen. Esto requiere O(n) de tiempo y O(n) de espacio para la lista de caracteres, algo inevitable porque las cadenas son inmutables.
def reverse_string(s):
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
return ''.join(chars)
print(reverse_string('hello')) # 'olleh'
print(reverse_string('Hannah')) # 'hannaH'
# Pythonic shortcut (creates new string):
print('hello'[::-1]) # 'olleh'Invertir las palabras de una oración
Invierta el orden de las palabras eliminando los espacios sobrantes. La solución más limpia en Python es usar split (gestiona varios espacios), invertir la lista con reverse y unirla con join. Para invertir in situ un arreglo de caracteres, invierta primero todo el arreglo y luego cada palabra individual. Este enfoque de dos pasadas requiere O(n) de tiempo y O(n) de espacio, algo inevitable con las cadenas de Python porque son inmutables.
def reverse_words(s):
words = s.split() # split and strip whitespace
words.reverse() # in-place reverse
return ' '.join(words) # single space between words
print(reverse_words(' hello world ')) # 'world hello'
print(reverse_words('a good example')) # 'example good a'
# One-liner:
print(' '.join(' hello world '.split()[::-1]))Detección sencilla de palíndromos
Una cadena es un palíndromo si es igual a su reverso. La comprobación más rápida en Python es s == s[::-1]. Para palíndromos que solo contienen caracteres alfanuméricos y no distinguen entre mayúsculas y minúsculas, como en la variante más habitual de las entrevistas, normalice primero la cadena: filtre los caracteres no alfanuméricos y conviértala a minúsculas; después, compárela. Ambos enfoques requieren O(n).
def is_palindrome(s):
# Filter and normalise
cleaned = ''.join(c.lower() for c in s if c.isalnum())
return cleaned == cleaned[::-1]
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # False
print(is_palindrome('Was it a car or a cat I saw?')) # TrueDetección de palíndromos: dos punteros
Para usar O(1) de espacio adicional, compruebe si la cadena es un palíndromo con dos punteros en lugar de usar slicing. Coloque left en 0 y right al final. Omita los caracteres no alfanuméricos, compare los caracteres restantes sin distinguir entre mayúsculas y minúsculas y devuelva False si no coinciden. Es más verboso, pero evita crear por completo la cadena limpia, algo importante cuando la memoria es limitada.
def is_palindrome_twoptr(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1; right -= 1
return True
print(is_palindrome_twoptr('A man, a plan, a canal: Panama')) # TrueExpansión desde el centro para hallar el palíndromo más largo
La técnica de expansión desde el centro encuentra la subcadena palindrómica más larga en O(n²) de tiempo y con O(1) de espacio adicional. Para cada carácter, en el caso de palíndromos de longitud impar, y para cada espacio entre caracteres, en el caso de palíndromos de longitud par, expándase hacia afuera mientras los caracteres coincidan. Lleve un registro del mejor par (inicio, fin) encontrado. Hay 2n-1 centros y cada expansión requiere O(n) en el peor caso.
def longest_palindrome(s):
best_start = best_end = 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1; right += 1
return left + 1, right - 1 # last valid bounds
for i in range(len(s)):
l, r = expand(i, i) # odd-length
if r - l > best_end - best_start:
best_start, best_end = l, r
l, r = expand(i, i + 1) # even-length
if r - l > best_end - best_start:
best_start, best_end = l, r
return s[best_start:best_end+1]
print(longest_palindrome('babad')) # 'bab' or 'aba'
print(longest_palindrome('cbbd')) # 'bb'Introducción al algoritmo de Manacher
El algoritmo de Manacher encuentra la subcadena palindrómica más larga en O(n) de tiempo gracias a la observación de que un palíndromo contenido en otro palíndromo más grande puede inicializarse a partir de una posición espejo. En las entrevistas rara vez se pide implementarlo, pero conviene saber que existe. La mayoría de los entrevistadores aceptan el enfoque de expansión desde el centro, con O(n²), como «suficientemente óptimo»; mencione Manacher como la solución teórica de O(n) si le piden una ampliación.
# Manacher's: O(n) longest palindromic substring
def manacher(s):
# Transform s into '#a#b#a#' to handle even/odd uniformly
t = '#' + '#'.join(s) + '#'
n = len(t)
P = [0] * n # P[i] = palindrome radius at i
center = right = 0
for i in range(n):
mirror = 2 * center - i
if i < right:
P[i] = min(right - i, P[mirror])
while (i + P[i] + 1 < n and i - P[i] - 1 >= 0
and t[i+P[i]+1] == t[i-P[i]-1]):
P[i] += 1
if i + P[i] > right:
center, right = i, i + P[i]
max_len = max(P)
center_idx = P.index(max_len)
start = (center_idx - max_len) // 2
return s[start:start+max_len]
print(manacher('babad')) # 'bab'Codificación por longitud de ejecución
La codificación por longitud de ejecución (RLE) comprime los caracteres repetidos consecutivamente: 'aaabbc' se convierte en 'a3b2c1'. Para implementarla, recorra la cadena con un puntero rápido hasta encontrar el final de cada secuencia, escriba el carácter y el número de repeticiones en una lista de salida y, después, únala. La entrada puede ser más corta que la salida codificada cuando las secuencias son cortas; compruebe siempre que la versión codificada sea más corta antes de devolverla.
def encode_rle(s):
if not s: return ''
parts = []
i = 0
while i < len(s):
char = s[i]
j = i
while j < len(s) and s[j] == char:
j += 1
count = j - i
parts.append(char + (str(count) if count > 1 else ''))
i = j
encoded = ''.join(parts)
return encoded if len(encoded) < len(s) else s
print(encode_rle('aaabbc')) # 'a3b2c'
print(encode_rle('abc')) # 'abc' (no compression gain)Decodificación de cadenas codificadas por longitud de ejecución
La decodificación de RLE lee los caracteres y las secuencias de dígitos que los siguen, expandiendo cada secuencia. En ocasiones, los entrevistadores presentan la variante de LeetCode en la que la codificación usa k[encoded_string] para repetir subcadenas; por ejemplo, 3[ab] → ababab. Esta variante anidada requiere una pila para gestionar varios niveles de anidamiento.
def decode_rle(s):
result = []
i = 0
while i < len(s):
char = s[i]; i += 1
num_str = ''
while i < len(s) and s[i].isdigit():
num_str += s[i]; i += 1
count = int(num_str) if num_str else 1
result.append(char * count)
return ''.join(result)
print(decode_rle('a3b2c')) # 'aaabbc'
print(decode_rle('a2b3c1')) # 'aabbbc'
# Nested bracket decode (LeetCode 394)
def decode_bracket(s):
stack = []
for c in s:
if c != ']':
stack.append(c)
else:
chars = []
while stack[-1] != '[':
chars.append(stack.pop())
stack.pop() # remove '['
k = int(stack.pop())
stack.append(''.join(reversed(chars)) * k)
return ''.join(stack)
print(decode_bracket('3[ab]')) # 'ababab'Palíndromo válido II: se permite una eliminación
Dada una cadena, devuelva True si puede convertirla en un palíndromo eliminando como máximo un carácter. Use dos punteros; ante la primera discrepancia, compruebe si s[left+1:right+1] o s[left:right] es un palíndromo; es decir, intente omitir cada uno de los caracteres que no coinciden. Si cualquiera de las dos opciones forma un palíndromo, devuelva True. Este enfoque voraz funciona porque omitir el carácter que no coincide es la única acción útil.
def valid_palindrome(s):
def is_pal(l, r):
while l < r:
if s[l] != s[r]: return False
l += 1; r -= 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# Try skipping either character
return is_pal(left+1, right) or is_pal(left, right-1)
left += 1; right -= 1
return True
print(valid_palindrome('aba')) # True
print(valid_palindrome('abca')) # True (delete 'c')
print(valid_palindrome('abc')) # FalsePartición de palíndromos I
Divida una cadena en todas las particiones posibles cuyas subcadenas sean palíndromos. Use búsqueda con vuelta atrás: en cada paso, pruebe todos los prefijos de la parte restante de la cadena; si un prefijo es un palíndromo, aplique recursión al resto. Calcule previamente una tabla booleana bidimensional is_pal[i][j] mediante programación dinámica por intervalos para que las comprobaciones de palíndromos requieran O(1), reduciendo la búsqueda con vuelta atrás general de O(n² × 2^n) a O(n × 2^n), un coste aceptable porque generar todas las particiones es, por naturaleza, exponencial.
def partition(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
for i in range(n):
dp[i][i] = True
for length in range(2, n+1):
for i in range(n-length+1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = length == 2 or dp[i+1][j-1]
result = []
def backtrack(start, path):
if start == n: result.append(path[:]); return
for end in range(start, n):
if dp[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition('aab')) # [['a','a','b'],['aa','b']]Palíndromo más corto: hash de cadenas
Encuentre el palíndromo más corto que se pueda obtener añadiendo caracteres al principio de una cadena. La idea clave es encontrar el prefijo palindrómico más largo de s y anteponer el reverso del sufijo restante. Para encontrar eficientemente el prefijo palindrómico más largo, use la función de fallo de KMP sobre la cadena s + '#' + reverse(s). El último valor de la función de fallo indica la longitud del prefijo palindrómico más largo.
def shortest_palindrome(s):
rev = s[::-1]
combined = s + '#' + rev # '#' prevents overlap
n = len(combined)
kmp = [0] * n
j = 0
for i in range(1, n):
while j > 0 and combined[i] != combined[j]:
j = kmp[j-1]
if combined[i] == combined[j]:
j += 1
kmp[i] = j
# kmp[-1] = length of longest palindromic prefix
to_add = rev[:len(s) - kmp[-1]]
return to_add + s
print(shortest_palindrome('aacecaaa')) # 'aaacecaaa'
print(shortest_palindrome('abcd')) # 'dcbabcd'Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió que: la detección de palíndromos con dos punteros requiere O(n) de tiempo y O(1) de espacio; cuando el espacio importa, prefiera siempre las comprobaciones basadas en índices a reservar espacio para una copia invertida, la expansión desde el centro encuentra la subcadena palindrómica más larga en O(n²), tratando cada una de las 2n-1 posiciones como un posible centro de palíndromo y la codificación por longitud de ejecución comprime las secuencias consecutivas en O(n), mientras que la decodificación requiere una pila para la variante anidada con corchetes. A continuación, exploraremos la ordenación de burbuja y la ordenación por inserción.
Preguntas frecuentes
¿La lección «Codificación, inversión y palíndromos de strings» es gratis?
Sí — el texto completo de «Codificación, inversión y palíndromos de strings» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Codificación, inversión y palíndromos de strings»?
Implemente la inversión de palabras in-place, la codificación por longitud de secuencias y la detección de palíndromos, incluida la técnica de expansión alrededor del centro. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Codificación, inversión y palíndromos de strings»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- API de strings de Python para entrevistas
- Ventana deslizante para subcadenas
- Anagramas y mapas de frecuencia de caracteres
- Codificación, inversión y palíndromos de strings