Longest Palindrome

Q: Qual é a complexidade de tempo do Longest Palindrome?

Tempo O(n) com contagem: cada letra adiciona 1 a um contador, e somar os pares lê 128 contadores, independentemente do tamanho de s . O espaço é O(1) . Ordenar e emparelhar vizinhos custa tempo O(n log n) e espaço O(n) .

FácilHashing Guloso

+10

Você recebe uma string s com letras maiúsculas e minúsculas. Reorganize suas letras para formar o maior palíndromo possível e retorne o comprimento desse palíndromo. Você pode colocar as letras em qualquer ordem e deixar algumas de fora, mas pode usar cada letra no máximo tantas vezes quantas ela aparece em s.

Letras maiúsculas e minúsculas são diferentes, então Aa não é um palíndromo.

Função

longestPalindrome(s: string) → integer

sstring: as letras que você pode usar, maiúsculas e minúsculas
Retornainteger: o comprimento do maior palíndromo que você pode formar com essas letras

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém apenas letras do alfabeto inglês, a a z e A a Z.
Você não precisa usar todas as letras.

Exemplos

Entrada: s = "coddyCode"
Saída: 5
Explicação: o aparece duas vezes e d três vezes; as demais letras aparecem uma vez. Um par de letras o, um par de letras d e uma letra restante no meio dão comprimento 5, por exemplo doCod.

Entrada: s = "Aa"
Saída: 1
Explicação: A e a são letras diferentes, então não existe nenhum par. Uma única letra sozinha é um palíndromo de comprimento 1.

Entrada: s = "xxxyyy"
Saída: 5
Explicação: Dois xs e dois ys formam pares, e uma letra restante fica no meio, como em xyxyx. O último y não tem par e fica de fora.

Para ir além

Você consegue retornar o próprio palíndromo mais longo, junto com seu comprimento, ainda em tempo O(n)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Como você pode reorganizar, a ordem de s não importa, apenas quantas vezes cada letra aparece. Em um palíndromo, cada letra tem uma cópia espelhada do outro lado, exceto por, no máximo, uma letra no meio. Portanto, conte as letras, mantenha cada par e adicione uma letra ao meio se sobrar alguma.

Ordene e emparelhe os vizinhos

Intuição

A ordenação coloca letras iguais lado a lado, de modo que cada par fica junto. Em xxxyyy, os xs nos índices 0 e 1 correspondem: pegue o par e avance duas posições. No índice 2, x e y são diferentes, então esse x fica sem par e você avança uma posição. Os ys nos índices 3 e 4 formam um segundo par, e o último y fica sozinho. Dois pares dão 4, mais uma letra do meio: 5.

Sobra uma letra exatamente quando os pares usam menos do que todas as n letras, então você não precisa de uma flag separada. A ordenação leva O(n log n) de tempo, e a cópia ordenada ocupa O(n) de espaço.

Algoritmo

Ordene as letras de s.
Percorra as letras ordenadas com um índice i. Se as letras nas posições i e i+1 forem iguais, adicione 2 ao comprimento e avance duas posições; caso contrário, avance uma posição.
Se o comprimento for menor que o número de letras, adicione 1 para a letra do meio.
Retorne o comprimento.

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

Conte cada letra

Intuição

A contagem fornece as mesmas informações sem ordenar. Mantenha um contador por código de caractere, 128 no total, para que A e a sejam contabilizados em contadores diferentes. Uma letra que aparece c vezes contribui com c arredondado para baixo até o número par mais próximo de letras.

Para coddyCode, os pares de o e d fornecem 4 letras. Sobram cinco letras, e qualquer uma delas pode ficar no meio: 5. Uma segunda letra sem par não teria um espelho.

Uma passagem por s preenche os contadores, e uma passagem pelos 128 contadores soma os pares: tempo O(n) e espaço extra O(1) (O(n) em R, que primeiro converte s em um vetor de códigos).

Algoritmo

Crie 128 contadores definidos como 0 e adicione 1 ao contador de cada letra de s.
Para cada contador, adicione ao comprimento a contagem arredondada para baixo até um número par.
Se o comprimento for menor que o comprimento de s, alguma contagem será ímpar, então adicione 1 para a letra do meio.
Retorne o comprimento.

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

Armadilhas e casos extremos

Descartar completamente as contagens ímpares. Uma letra que aparece 3 vezes ainda fornece um par: xxxyyy resulta em 5, não em 1.
Adicionar 1 para cada contagem ímpar. Apenas uma letra pode ficar no meio, então xxxyyy resulta em 5, não em 6.
Tratar A e a como a mesma letra. Aa não tem nenhum par, então a resposta é 1, não 2.
Dimensionar os contadores apenas para a até z. As letras maiúsculas têm códigos de 65 a 90 e ficam fora desse intervalo; use o código completo do caractere como índice.

Perguntas frequentes3

Qual é a diferença entre o maior palíndromo e a maior substring palindrômica?

Aqui você pode reorganizar as letras, então só as quantidades importam, e contá-las resolve o problema em O(n). Longest Palindromic Substring pede um palíndromo que já apareça como um bloco de letras consecutivas e requer outro método, como expandir a partir de cada centro. Para abab, este problema responde 4 (abba), enquanto a versão de substring responde 3 (aba).

Qual é a complexidade de tempo do Longest Palindrome?

Tempo O(n) com contagem: cada letra adiciona 1 a um contador, e somar os pares lê 128 contadores, independentemente do tamanho de s. O espaço é O(1). Ordenar e emparelhar vizinhos custa tempo O(n log n) e espaço O(n).

Você precisa usar todas as letras de s?

Não. Cada par entra, e no máximo uma letra sem par entra no meio. Portanto, a resposta é o comprimento de s quando no máximo uma letra tem uma contagem ímpar; caso contrário, é o comprimento de s menos o número de letras com contagem ímpar, mais 1.

def longestPalindrome(s):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

s = "coddyCode"

Saída Esperada