Longest Palindrome

Q: Qual è la complessità temporale di Longest Palindrome?

Tempo O(n) con il conteggio: ogni lettera aggiunge 1 a un contatore e sommare le coppie richiede di leggere 128 contatori, qualunque sia la lunghezza di s . Lo spazio è O(1) . Ordinare e abbinare gli elementi vicini richiede un tempo O(n log n) e uno spazio O(n) .

FacileHashing Greedy

+10

Ricevi una stringa s composta da lettere maiuscole e minuscole. Riordina le sue lettere per costruire il palindromo più lungo possibile e restituisci la lunghezza di quel palindromo. Puoi disporre le lettere in qualsiasi ordine e ometterne alcune, ma puoi usare ogni lettera al massimo tante volte quante appare in s.

Le lettere maiuscole e minuscole sono considerate diverse, quindi Aa non è un palindromo.

Funzione

longestPalindrome(s: string) → integer

sstring: le lettere che puoi usare, sia maiuscole che minuscole
Restituisceinteger: la lunghezza del palindromo più lungo che puoi costruire con quelle lettere

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo lettere inglesi, da a a z e da A a Z.
Non devi usare tutte le lettere.

Esempi

Input: s = "coddyCode"
Output: 5
Spiegazione: o compare due volte e d tre volte, il resto una volta. Una coppia di o, una coppia di d e una lettera rimanente al centro danno una lunghezza di 5, per esempio doCod.

Input: s = "Aa"
Output: 1
Spiegazione: A e a sono lettere diverse, quindi non esiste alcuna coppia. Una singola lettera da sola è un palindromo di lunghezza 1.

Input: s = "xxxyyy"
Output: 5
Spiegazione: Due x e due y formano delle coppie, e una lettera rimanente va al centro, come in xyxyx. L’ultima y non ha una compagna e resta fuori.

Per approfondire

Riesci a restituire uno dei palindromi più lunghi, insieme alla sua lunghezza, sempre in tempo O(n)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Poiché puoi riordinare s, l’ordine non importa: conta solo quante volte compare ogni lettera. In un palindromo ogni lettera ha una copia speculare dall’altro lato, tranne al massimo una lettera al centro. Quindi conta le lettere, conserva ogni coppia e aggiungi una lettera al centro se ne rimane qualcuna.

Ordina e abbina i vicini

Intuizione

L'ordinamento mette le lettere uguali una accanto all'altra, così ogni coppia è affiancata. In xxxyyy, le x agli indici 0 e 1 corrispondono: prendi la coppia e spostati di due posizioni. All'indice 2, x e y sono diverse, quindi quella x resta senza coppia e ti sposti di una posizione. Le y agli indici 3 e 4 formano una seconda coppia, e l'ultima y resta da sola. Due coppie danno 4, più una lettera centrale: 5.

Una lettera avanza esattamente quando le coppie hanno usato meno di tutte le n lettere, quindi non serve un flag separato. L'ordinamento richiede un tempo O(n log n) e la copia ordinata occupa uno spazio O(n).

Algoritmo

Ordina le lettere di s.
Esamina le lettere ordinate con un indice i. Se le lettere in corrispondenza di i e i+1 sono uguali, aggiungi 2 alla lunghezza e spostati di due posizioni; altrimenti spostati di una posizione.
Se la lunghezza è inferiore al numero di lettere, aggiungi 1 per la lettera centrale.
Restituisci la lunghezza.

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

Conta ogni lettera

Intuizione

Il conteggio fornisce le stesse informazioni senza ordinare. Tieni un contatore per ogni codice carattere, 128 in tutto, così A e a finiscono in contatori diversi. Una lettera che compare c volte fornisce c arrotondato per difetto al numero pari di lettere.

Per coddyCode, le coppie di o e d danno 4 lettere. Ne restano fuori cinque e ognuna di esse può occupare il centro: 5. Una seconda lettera spaiata non avrebbe un corrispondente speculare.

Un passaggio su s riempie i contatori e un passaggio sui 128 contatori somma le coppie: tempo O(n) e spazio extra O(1) (O(n) in R, che prima converte s in un vettore di codici).

Algoritmo

Crea 128 contatori impostati a 0 e aggiungi 1 al contatore di ogni lettera di s.
Per ogni contatore, aggiungi alla lunghezza il conteggio arrotondato per difetto a un numero pari.
Se la lunghezza è inferiore alla lunghezza di s, qualche conteggio è dispari, quindi aggiungi 1 per la lettera centrale.
Restituisci la lunghezza.

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

Trappole e casi limite

Ignorare del tutto i conteggi dispari. Una lettera che compare 3 volte fornisce comunque una coppia: xxxyyy dà 5, non 1.
Aggiungere 1 per ogni conteggio dispari. Solo una lettera può stare al centro, quindi xxxyyy dà 5, non 6.
Considerare A e a la stessa lettera. Aa non contiene coppie, quindi la risposta è 1, non 2.
Dimensionare i contatori solo per a–z. Le lettere maiuscole hanno codici da 65 a 90 e non rientrano in quell'intervallo; usa come indice il codice completo del carattere.

Domande frequenti3

In che modo il Palindromo più lungo è diverso dalla Sottostringa palindroma più lunga?

Qui puoi riordinare le lettere, quindi contano solo le quantità e contarle permette di risolvere il problema in O(n). La sottostringa palindromica più lunga richiede un palindromo che sia già presente come blocco di lettere consecutive e necessita di un altro metodo, come espandersi attorno a ciascun centro. Per abab questo problema restituisce 4 (abba), mentre la versione della sottostringa restituisce 3 (aba).

Qual è la complessità temporale di Longest Palindrome?

Tempo O(n) con il conteggio: ogni lettera aggiunge 1 a un contatore e sommare le coppie richiede di leggere 128 contatori, qualunque sia la lunghezza di s. Lo spazio è O(1). Ordinare e abbinare gli elementi vicini richiede un tempo O(n log n) e uno spazio O(n).

Devi usare ogni lettera di s?

No. Ogni coppia viene inserita e al massimo una lettera spaiata viene inserita al centro. Quindi la risposta è la lunghezza di s quando al massimo una lettera ha un conteggio dispari; altrimenti è la lunghezza di s meno il numero di lettere con un conteggio dispari, più 1.

def longestPalindrome(s):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

s = "coddyCode"

Output atteso