Mais longa subsequência palindrômica até mesmo (com caracteres adjacentes distintos, exceto para as letras do centro 2)

Question

Você recebe uma string S contendo caracteres em letras minúsculas. Você precisa encontrar o comprimento da maior subsequência de S que satisfaz o seguinte padrão: X1, x2, x3 ... xn, xn, ... x3, x2, x1 Onde XI é algum caractere de S. A única restrição é que nenhum caractere adjacente deve ser o mesmo, exceto xn, isto é xi!= x (i + 1) para todos os 1 <= i < n.

Entrada: a string: s
Saída: o inteiro: 2n
Restrição: 1 <= | s | <= 10 ^ 3

Entrada de amostra 1: "ACDBDEA"
Saída de amostra 1: 4
Explicação: "Adda" é a subsequência mais longa após o padrão dado.

Entrada de amostra 2: "abbacdeedc"
Saída de amostra 2: 6
Explicação: "CDEEDC" é a subsequência mais longa após o padrão dado.

Entrada de amostra 3: "Taker"
Saída de amostra 3: 0 Explicação: Nenhuma subsequência segue o padrão dado.

---

.

Esta pergunta foi feita em uma entrevista de codificação e eu não sabia como resolvê-lo. Eu entendi como encontrar a mais longa subsequência palindrômica, mas não sei como implementar a parte distinta do personagem adjacente. Por favor ajude. Pseudocódigo é bom.

Answer 1

regra de ouro

Aqui está a regra de ouro da programação dinâmica.

Quando as soluções para subproblemas menores não podem ser combinadas em soluções para subproblemas maiores devido a informações ausentes, estenda os subproblemas por adicionando parâmetros que dão essa informação ausente.

---

.

primeira tentativa

$ S $ é uma sequência de $ n $ letras ou, $ s [0: n]. $

Deixe $ l [i] [J] $ ser o comprimento da subsequência palindrômica mais longa da $ s [i : j] $ . É fácil descobrir os casos de base e, aumentando $ i $ e / ou diminuindo $ J $ , as relações de recorrência para $ l [i] [J] $ .

Agora adicione a condição de comprimento par. Deixe $ E [i] [j] $ ser o comprimento da subsequência palindrômica par comprida mais longa da $ s [i : j] $ . Podemos descobrir os casos de base e as relações de recorrência para $ e [i] [J] $ , semelhante aos da $ L [i] [j] $ .

Agora adicione a condição de letras adjacentes distintas, isto é, nenhuma letra pode aparecer duas vezes seguidas, exceto a letra no centro. Deixe $ D [i] [j] $ ser o comprimento da mais longa duração distinta-adjacente-adjacente-adjacente - subsequência palindrômica da $ S [i: j] $ . Como você poderia ter notado, não podemos descobrir as relações de recorrência para $ D [i] [J] $ , desde que estendendo tal subsequência a um mais tempo pode introduzir repetidos letras.

A regra de ouro vem para resgatar. Adicione outro parâmetro que classifica a letra no final da subsequência mais longa encontrada até agora, para que possamos determinar como estender essa subsequência corretamente.

Deixe $ D [i] [J] [\ lambda] $ seja o comprimento da mais longa duração distinta-adjacente-adjacente-adjacente - subsequência palindrômica de $ s [i: j] $ que termina na letra $ \ lambda $ . Isto é, vamos calcular $ D [i] [j] [\ text {'} a \ text {'}] $ , $ D [i] [j] [\ text {'} b \ text {'}] $ , $ D [i] [J] [ texto {'} c \ text {'}] $ , $ \ cdoz $ , $ D [i ] [j] [\ text {'} z \ text {'}] $ .

• A resposta final é a maior de $ \ max_ \ lambda d [0] [N-1] [\ lambda] $ e $ 0 $ .

• Suponha que a primeira $ \ text {'} a \ text {'} $ na $ s $ em ou após $ s [i] $ aparece em $ s [\ vec {i _ {\ text { '} a \ text {'}}}] $ . Suponha a primeira $ \ text {'} a \ text {'} $ em $ s $ aparece em $ s [\ overleftarrow {j _ {\ text {'} a \ text {'}}}] $ antes $ s [j] $ pesquisado para trás. $ \ vec {i _ {\ text {'} a \ text {'}}} $ ou $ \ overleftarrow {j_ {\ text {'} a \ text {'}}} $ é definido como $ - 1 $ se $ \ text {'} a \ text {'} $ não é encontrado respectivamente. Temos, para $ j \ ge i + 2 $ ,

  $$ D [i] [J] [\ text {'} a \ text {'}]=begin} \ max (2, 2 + max _ {\ mu \ not=text {'} a \ text {'}} d [\ vec {i _ {\ text {'} a \ text}}} + 1] [\ OverleFtarrow {j _ {\ text {'} a \ text {'}}}] [}}}] [\ m]) & \ text {se} 0 \ le \ vec {i _ {\ text {'} a \ text {'} }} \ lt \ overleftarrow {j _ {\ text {'} a \ text {'}}}, \\ -1 & \ text {de outra forma,} \\ \ fim {casos} $$ onde $ \ Mu $ passa por todas as letras em inglês minúsculas.

• O caso da base é $$ D [i] [i] [\ text {'} a \ text {'}]= 0. $$

generalizando $ {'} a \ text {'} $ para variável $ \ lambda $ , podemos escrever a relação de recorrência e caso base para $ D [i] [J] [\ Lambda] $ .

Observe que com as informações extras incorporadas na $ \ lambda $ parâmetro, é fácil deduzir a relação de recorrência.

Enquanto esta tentativa é bem sucedida, podemos fazer melhor.

---

.

segunda tentativa

Podemos simplificar os subproblemas.

Deixe $ f [i] [j] $ ser o comprimento do mais longo desse subsequência que começa na $ s [i] $ e termina em

PAN Classe="contêiner matemática"> $ s [J] $ . Então nós temos

$$ f [i] [J]=begin {casos} \ max (2, 2 + max _ {\ mu \ ng= s [i]} f [\ vec {i_ \ mu}] [\ Overleftarrow {j_ \ mu}]) e \ text {if} s [i]= S [j], \\ -1 & \ text {de outra forma,} \\ \ fim {casos} $$ Onde $ - 1 $ significa "não encontrado". Para todas as letras de inglês minúsculas $ \ Mu $ , $ s [\ vec {i_ \ mu}] $ é a primeira $ \ mu $ que aparece após $ s [i] $ e $ s [\ OverleFTarrow {j_ \ mu}] $ é a primeira $ \ mu $ que aparece antes $ s [j] $ procurou para trás. Se um deles não puder ser encontrado, o termo $ f [\ vec {i_ \ mu}] [\ Overleftarrow {j_ \ mu}] $ é ignorado. .

A resposta final é a maior de $ \ max_ {i, j} f [i] [J] $ e 0.