Longest Palindrome

Q: ¿Cuál es la complejidad temporal de Longest Palindrome?

Tiempo O(n) contando: cada letra suma 1 a un contador, y sumar los pares requiere leer 128 contadores, sea cual sea la longitud de s . El espacio es O(1) . Ordenar y emparejar elementos vecinos cuesta un tiempo O(n log n) y un espacio O(n) .

FácilHashing Voraz

+10

Recibes una cadena s formada por letras mayúsculas y minúsculas. Reordena sus letras para formar el palíndromo más largo que puedas y devuelve la longitud de ese palíndromo. Puedes poner las letras en cualquier orden y omitir algunas, pero puedes usar cada letra como máximo tantas veces como aparezca en s.

Las mayúsculas y las minúsculas son letras diferentes, así que Aa no es un palíndromo.

Función

longestPalindrome(s: string) → integer

sstring: las letras que puedes usar, en mayúsculas y minúsculas
Devuelveinteger: la longitud del palíndromo más largo que puedes formar con esas letras

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo letras inglesas, de la a a la z y de la A a la Z.
No tienes que usar todas las letras.

Ejemplos

Entrada: s = "coddyCode"
Salida: 5
Explicación: o aparece dos veces y d tres veces; las demás, una vez. Un par de o, un par de d y una letra restante en el medio dan una longitud de 5, por ejemplo, doCod.

Entrada: s = "Aa"
Salida: 1
Explicación: A y a son letras diferentes, así que no existe ningún par. Una letra por sí sola es un palíndromo de longitud 1.

Entrada: s = "xxxyyy"
Salida: 5
Explicación: Dos x y dos y forman pares, y una letra sobrante va en el medio, como en xyxyx. La última y no tiene pareja y se queda fuera.

Para ir más allá

¿Puedes devolver un palíndromo de longitud máxima junto con su longitud, todavía en tiempo O(n)?

Pistas

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

0 de 3 abiertas

Solución

Como puedes reorganizarlo, el orden de s no importa, solo cuántas veces aparece cada letra. En un palíndromo, cada letra tiene una copia simétrica al otro lado, excepto como máximo una letra en el centro. Así que cuenta las letras, conserva cada par y añade una letra central si sobra alguna.

Ordena y empareja a los vecinos

Intuición

Ordenar coloca las letras iguales una junto a otra, de modo que cada par queda lado a lado. En xxxyyy, las x de los índices 0 y 1 coinciden: toma el par y avanza dos posiciones. En el índice 2, x y y son distintas, así que esa x queda sin pareja y avanzas una posición. Las y de los índices 3 y 4 forman un segundo par, y la última y queda sola. Dos pares dan 4, más una letra central: 5.

Una letra queda sobrante exactamente cuando los pares usan menos de las n letras, así que no necesitas una bandera aparte. Ordenar cuesta O(n log n) de tiempo y la copia ordenada ocupa O(n) de espacio.

Algoritmo

Ordena las letras de s.
Recorre las letras ordenadas con un índice i. Si las letras en i y i+1 son iguales, suma 2 a la longitud y avanza dos posiciones; de lo contrario, avanza una posición.
Si la longitud es menor que el número de letras, suma 1 por la letra del medio.
Devuelve la longitud.

def longestPalindrome(s):
    letters = sorted(s)
    n = len(letters)
    length = 0
    i = 0
    while i + 1 < n:
        if letters[i] == letters[i + 1]:
            length += 2  # a pair: one copy on each side of the middle
            i += 2
        else:
            i += 1
    # A letter left without a partner can stand alone in the middle
    if length < n:
        length += 1
    return length

Cuenta cada letra

Intuición

Contar proporciona la misma información sin ordenar. Mantén un contador por cada código de carácter, 128 en total, para que A y a queden en contadores distintos. Una letra que aparece c veces aporta c redondeado hacia abajo al número par de letras.

Para coddyCode, los pares de o y d suman 4 letras. Quedan fuera cinco letras, y cualquiera de ellas puede ocupar el centro: 5. Una segunda letra sin pareja no tendría reflejo.

Una pasada por s llena los contadores y una pasada por los 128 contadores suma los pares: tiempo O(n) y espacio adicional O(1) (O(n) en R, que primero convierte s en un vector de códigos).

Algoritmo

Crea 128 contadores establecidos en 0 y suma 1 al contador de cada letra de s.
Para cada contador, suma a la longitud el recuento redondeado hacia abajo a un número par.
Si la longitud es menor que la longitud de s, algún recuento es impar, así que suma 1 para la letra del medio.
Devuelve la longitud.

def longestPalindrome(s):
    counts = [0] * 128  # one counter per character code, so 'A' and 'a' differ
    for ch in s:
        counts[ord(ch)] += 1
    length = 0
    for count in counts:
        length += count // 2 * 2  # every pair fits, one copy on each side
    # Fewer letters used than s has: some count is odd, so one letter can go in the middle
    if length < len(s):
        length += 1
    return length

Errores comunes y casos límite

Descartar por completo los recuentos impares. Una letra que aparece 3 veces sigue aportando un par: xxxyyy da 5, no 1.
Sumar 1 por cada recuento impar. Solo cabe una letra en el centro, así que xxxyyy da 5, no 6.
Tratar A y a como la misma letra. Aa no tiene ningún par, así que la respuesta es 1, no 2.
Dimensionar los contadores solo para a a z. Las letras mayúsculas tienen códigos del 65 al 90 y quedan fuera de ese rango; indexa usando el código completo del carácter.

Preguntas frecuentes3

¿En qué se diferencia el palíndromo más largo de la subcadena palindrómica más larga?

Aquí puedes reorganizar las letras, así que solo importan las cantidades y contarlas lo resuelve en O(n). Longest Palindromic Substring pide un palíndromo que ya aparezca como un bloque de letras consecutivas y requiere otro método, como expandir alrededor de cada centro. Para abab, este problema da como respuesta 4 (abba); la versión de subcadena, 3 (aba).

¿Cuál es la complejidad temporal de Longest Palindrome?

Tiempo O(n) contando: cada letra suma 1 a un contador, y sumar los pares requiere leer 128 contadores, sea cual sea la longitud de s. El espacio es O(1). Ordenar y emparejar elementos vecinos cuesta un tiempo O(n log n) y un espacio O(n).

¿Tienes que usar todas las letras de s?

No. Cada pareja se incluye, y como máximo una letra sin pareja se coloca en el medio. Así que la respuesta es la longitud de s cuando como máximo una letra aparece una cantidad impar de veces; de lo contrario, es la longitud de s menos el número de letras que aparecen una cantidad impar de veces, más 1.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "coddyCode"

Salida Esperada