Subsornica palindromica più lunga anche di lunghezza (con caratteri distinti adiacenti ad eccezione del centro 2 lettere)

Question

Ti viene assegnata una stringa contenente caratteri inglesi minuscoli. Devi trovare la lunghezza della più grande successiva successiva di s che soddisfi il seguente schema: X1, x2, x3 ... xn, xn, ... x3, x2, x1 dove Xi è un certo carattere di S. L'unico vincolo è che nessun carattere adiacente dovrebbe essere lo stesso tranne Xn, cioè xi!= x (I + 1) per tutti 1 <= I < n.

Ingresso: la stringa: s
Uscita: il numero intero: 2n
Vincolo: 1 <= | s | <= 10 ^ 3

Ingresso campione 1: "ACDBDEA"
Esecuzione del campione 1: 4
Spiegazione: "Adda" è la più lunga successiva seguente il modello dato.

Ingresso campione 2: "AbbacDeedc"
Esempio di uscita 2: 6
Spiegazione: "CDEDC" è la più lunga successiva seguente il modello dato.

Ingresso campione 3: "Taker"
Esempio di uscita 3: 0
Spiegazione: Nessuna successiva segue il modello dato.

---

.

Questa domanda è stata chiesta in un'intervista di codifica e non sapevo come risolverlo. Ho capito come trovare la più lunga successiva successiva palindroma ma non so come implementare la parte distinta del carattere adiacente. Per favore aiuto. Pseudocodice va bene.

Answer 1

regola d'oro

Ecco la regola dorata della programmazione dinamica.

Quando le soluzioni a subproblemi più piccole non possono essere combinate in soluzioni a subproblemi più grandi a causa di informazioni mancanti, estendere i sottoproblemi di aggiungendo parametri che danno quelle informazioni mancanti.

.

Primo tentativo

$ s $ è una sequenza di $ N $ lettere o, $ s [0: n]. $

Let $ L [I] [J] $ Sii la lunghezza della più lunga successiva Palindromic successiva di $ s [i : J] $ . È facile capire i casi base e, aumentando $ i $ e / o diminuendo $ J $ , i rapporti di ricorrenza per $ l [i] [j] $ .

Ora aggiungi la condizione di lunghezza anche. Let $ e [i] [j] $ Sii la lunghezza della più lunga seconda lunghezza della lunghezza della seconda lunghezza di $ s [i : J] $ . Possiamo capire i casi base e i rapporti di recidiva per $ e [i] [j] $ , simile a quelli di $ L [i] [j] $ .

Ora aggiungere la condizione di distinte lettere adiacenti, I.e., nessuna lettera può apparire due volte in fila, ad eccezione della lettera al centro. Let $ D [I] [j] $ Sii la lunghezza della più lunga lunghezza pari-lunghezza-adiacente-lettera adiacente alla successive di $ S [i: j] $ . Come potresti aver notato, non possiamo capire i rapporti di recidiva per $ d [i] [j] $ , poiché estendere tale successiva a uno più a lungo potrebbe introdurre ripetuto Lettere.

La regola d'oro viene in salvataggio. Aggiungi un altro parametro che classifica la lettera alla fine della successiva più lunga trovata finora, in modo che possiamo determinare come estendere correttamente la successiva successiva.

Let $ D [i] [J] [\ Lambda] $ Sii la lunghezza della più lunga durata di lunghezza nea-lunghezza-lettera acciamata-lettera adiacente alla successive di $ s [i: j] $ che termina nella lettera $ \ Lambda $ . Cioè, calcoleremo $ d [i] [j] [\ testo {'} A \ testo {'}] $ , $ D [i] [j] [\ testo {'} b \ testo {'}] $ , $ d [i] [j] [\ testo {'} c \ testo {'}] $ , $ \ cdots $ , $ d [i ] [J] [\ testo {'} z \ testo {'}] $ .

.

• La risposta finale è la più grande di $ \ max_ \ lambda d [0] [n-1] [\ Lambda] $ e $ 0 $ .

• Supponi la prima $ \ text {'} A \ testo {'} $ in $ s $ s a o dopo $ s [i] $ appare a $ s [\ vec {i _ {\ testo { '} A \ testo {'}}}] $ . Supponiamo che il primo $ \ text {'} A \ testo {'} $ in $ s $ appare a $ s [\ overleftarrow {j _ {\ text {'} a \ text {'}}}] $ prima $ s [J] $ cercato all'indietro. $ \ vec {i _ {\ text {'} A \ text {'}}} $ o $ \ overleftarrow {j_ {\ testo {'} A \ testo {'}}} $ è impostato su $ - 1 $ se $ \ testo {'} A \ testo {'} $ non è stato trovato rispettivamente. Abbiamo, per $ j \ ge i + 2 $ ,

  $$ d [i] [j] [\ text {'} A \ text {'}]=Begin {casi} \ max (2, 2 + \ max _ {\ mu \ not=text {'} A \ testo {'}} d [\ vec {i _ {\ text {'} A \ testo {'}}} + 1] [\ OverleFtarrow {J _ {\ Text {'} A \ Text {'}}}] [\ MU]) & \ Text {IF} 0 \ LE \ VEC {I _ {\ TEXT {'} A \ TEXT {'} }}} \ lt \ overleftarrow {j _ {\ testo {'} A \ testo {'}}}, \\ -1 e \ testo {altrimenti,} \\ \ end {casi} $$ dove $ \ MU $ corre attraverso tutte le lettere inglesi minuscole.

• Il caso di base è $$ d [i] [i] [\ text {'} A \ testo {'}]= 0. $$

Generalizzazione $ \ text {'} A \ testo {'} $ in variabile $ \ Lambda $ , possiamo scrivere la relazione di ricorrenza e il caso base per $ d [i] [j] [\ Lambda] $ .

Si noti che con le informazioni aggiuntive incarnate nella $ \ Lambda $ Parametro, è facile dedurre la relazione di ricorrenza.

Mentre questo tentativo ha successo, possiamo fare meglio.

---

.

Secondo tentativo

Possiamo semplificare i sottoproblemi.

Let $ f [i] [j] $ Sii la lunghezza della più lunga successiva che inizia a $ s [I] $ e termina a

Pan Class="Math-Container"> $ s [j] $ . Quindi abbiamo

$$ f [i] [j]=begin {casi} \ MAX (2, 2 + \ MAX _ {\ MU \ NOT= S [I]} F [\ VEC {I_ \ MU}] [\ OverleFtarrow {J_ \ MU}]) & \ TEXT {IF} S [I]= S [j], \\ -1 e \ testo {altrimenti,} \\ \ end {casi} $$ Dove $ - 1 $ Stand per "non trovato". Per tutte le lettere in inglese minuscola $ \ MU $ , $ s [\ vec {i_ \ mu}] $ è la prima $ \ MU $ che appare dopo $ s [i] $ e $ s [\ overleftarrow {j_ \ MU}] $ è la prima $ \ MU $ che appare prima di $ s [j] $ cercato all'indietro. Se uno di questi non può essere trovato, il termine $ f [\ vec {i_ \ mu}] [\ overleftarrow {j_ \ mu}] $ è ignorato. .

La risposta finale è la più grande di $ \ max_ {i, j} f [i] [j] $ e 0.