Subsecuencia palindrómica más larga incluso larga (con caracteres adyacentes distintos, excepto las letras del centro 2)

Question

Se le da una cadena que contiene caracteres en inglés en minúsculas. Debe encontrar la longitud de la mayor subsecuencia de S que satisfaga el siguiente patrón: X1, x2, x3 ... xn, xn, ... x3, x2, x1 donde Xi es un poco de carácter de S. La única restricción es que ningún carácter adyacente debe ser el mismo, excepto xn, ¡eso es xi!= x (i + 1) para todo 1 <= i < n.

Entrada: la cadena: s
Salida: El entero: 2n
Restricción: 1 <= | S | <= 10 ^ 3

Entrada de muestra 1: "ACDBDEA"
Salida de muestra 1: 4
Explicación: "Adda" es la subsecuencia más larga siguiente al patrón dado.

Entrada de muestra 2: "abbacdeedc"
Salida de muestra 2: 6
Explicación: "CDEEDC" es la subsecuencia más larga siguiente al patrón dado.

Entrada de muestra 3: "Taker"
Salida de muestra 3: 0
Explicación: ninguna subsecuencia sigue el patrón dado.

---

Esta pregunta se solicitó en una entrevista de codificación y no sabía cómo resolverlo. Entendí cómo encontrar la posterior posterior palindrómica más larga, pero no sabe cómo implementar la parte de carácter adyacente distinta. Por favor ayuda. Pseudocódigo está bien.

Answer 1

regla de oro

Aquí está la regla de oro de la programación dinámica.

Cuando las soluciones a subproblemas más pequeños no se pueden combinar en soluciones a los subproblemas más grandes debido a la información faltante, extienda los subproblemes por agregando parámetros que dan esa información faltante.

---

primer intento

$ s $ es una secuencia de $ n $ letras o, $ s [0: n]. $

Let $ l [I] [J] $ Sé la longitud de la posterior posterior palindrómica más larga de $ s [i : j] $ . Es fácil averiguar los casos base y, al aumentar $ i $ y / o / o decreciente $ j $ , las relaciones de recurrencia para $ l [I] [J] $ .

Ahora agregue la condición de la longitud uniforme. Deje que $ E [I] [J] $ sea la longitud de la posterior posterior palindrómica de la longitud más larga de $ s [i : j] $ . Podemos averiguar los casos base y las relaciones de recurrencia para $ e [i] [j] $ , similar a las de $ L [I] [J] $ .

Ahora agregue la condición de distintas letras adyacentes, es decir, ninguna letra puede aparecer dos veces seguidas, excepto la letra en el centro. Deje que $ d [i] [j] $ sea la longitud de la longitud de la subsecuencia palindrómica de longitud más larga de $ S [i: j] $ . Como podría haber señalado, no podemos averiguar las relaciones de recurrencia para $ d [i] [j] $ , ya que extendiendo una posterior posterior a una más larga, podría introducir repetidas letras.

La regla de oro viene a rescatar. Agregue otro parámetro que clasifique la letra al final de la subsecuencia más larga encontrada hasta ahora, para que podamos determinar cómo extender esa subsecuencia correctamente.

Let $ D [I] [J] [\ lambda] $ Sé la longitud de la posterior posterior palíndrómica de una letra más larga y de longitud más larga de $ s [i: j] $ que termina en la letra $ \ lambda $ . Es decir, competiremos $ d [I] [j] [\ texto {'} A \ texto {'}] $ , $ d [i] [j] [\ texto {'} b \ texto {'}] $ , $ d [i] [j] [\ Texto {'} C \ Text {'}] $ , $ \ cdots $ , $ d [i ] [j] [\ texto {'} Z \ texto {'}] $ .

• La respuesta final es la más grande de $ \ max_ \ lambda d [0] [N-1] [\ lambda] $ y $ 0 $ .

• Supongamos el primer $ \ texto {'} A \ texto {'} $ en $ s $ en o después de $ s [i] $ aparece en $ s [\ vec {i _ {\ texto { '} A \ Text {'}}}] $ . Supongamos que el primer $ \ texto {'} A \ texto {'} $ en $ s $ aparece en $ s [\ soverleftarrow {j _ {\ texto {'} A \ texto {'}}}] $ antes de $ s [J] $ buscado hacia atrás. $ \ vec {i _ {\ texto {'} A \ texto {'}}} $ o $ \ soverleftarrow {j_ {\ texto {'} A \ texto {'}}} $ se establece en $ - 1 $ si $ \ texto {'} A \ texto {'} $ no se encuentra respectivamente. Tenemos, para $ j \ ge i + 2 $ ,

  $$ D [I] [J] [\ Text {'} A \ Text {'}]=comienzan {casos} \ max (2, 2 + \ max _ {\ mu \ no=texto {'} A \ texto {'}} D [\ VEC {I _ {\ texto {'} A \ texto {'}}} + 1] [\ SOBRELEFTARROW {J _ {\ texto {'} A \ texto {'}}}] [\ mu]) & \ texto {if} 0 \ le \ vec {i \ \ {\ texto {'} A \ texto {'} }} \ lt \ soverleftarrow {j _ {\ texto {'} A \ texto {'}}}, \\ -1 & \ texto {de otra manera,} \\ \ End {casos} $$ donde $ \ mu $ se ejecuta a través de todas las letras en inglés en minúsculas.

• El caso base es $$ d [i] [i] [\ texto {'} A \ texto {'}]= 0. $$

generalizando $ \ texto {'} A \ texto {'} $ a variable $ \ lambda $ , podemos escribir la relación de recurrencia y el caso base para $ d [i] [j] [\ lambda] $ .

Tenga en cuenta que con la información adicional incorporada en el $ \ lambda $ parámetro, es fácil deducir la relación de recurrencia.

Si bien este intento tiene éxito, podemos hacerlo mejor.

---

segundo intento

Podemos simplificar los subproblemes.

Let $ F [I] [J] $ Sé la duración de la posterior posterior más larga que comienza en $ s [i] $ y termina a

Pan Class="Math-Container"> $ S [J] $ . Entonces tenemos

$$ F [I] [J]=Comenzar {casos} \ max (2, 2 + \ max _ {\ mu \ no= s [i]} f [\ vec {i_ \ mu}] [\ soverleftarrow {j_ \ mu}]) & \ texto {if} s [i]= S [j], \\ -1 & \ texto {de otra manera,} \\ \ End {casos} $$ donde $ - 1 $ significa "no encontrado". Para todas las letras en inglés en minúsculas $ \ mu $ , $ s [\ vec {i_ \ mu}] $ es el primer $ \ MU $ que aparece después de $ s [i] $ y $ s [\ spanleftarrow {j_ \ mu}] $ es el primer $ \ mu $ que aparece antes de $ s [J] $ buscado hacia atrás. Si no se puede encontrar uno de ellos, el término $ f [\ vec {i_ \ mu}] [\ soverleftarrow {j_ \ mu}] $ se ignora.

La respuesta final es la más grande de $ \ max_ {i, j} F [i] [j] $ y 0.