Самая длинная равномерная палиндромная подпоследовательность (с отчетливыми прилегающими персонажами, кроме центральных букв)

Question

Вам дан строка S, содержащая строчные английские символы. Вам нужно найти длину самой большой подпоследовательности S, которая удовлетворяет следующему рисунку: X1, x2, x3 ... xn, xn, ... x3, x2, x1 Где XI - какой-то символ S. Единственное ограничение, в том, что ни один соседний символ не должен быть одним и тем же, кроме Xn, то есть Xi!= x (I + 1) для всех 1 <= I < п.

Вход: Строка: s
Выход: целое число: 2n
Ограничение: 1 <= | S | <= 10 ^ 3

Пример ввода 1: «ACDBDEA»

Образец вывода 1: 4
Объяснение: «ADDA» - самая длинная подпоследовательность после данного шаблона.

Пример ввода 2: «ABBACDEEDC»

Образец вывода 2: 6
Объяснение: «CDEEDC» - самая длинная подпоследовательность после данного шаблона.

Пример ввода 3: "Taker"


Образец вывода 3: 0
Объяснение: Нет подпоследовательности не следует данному шаблону.

---

Этот вопрос был задан в кодирующем интервью, и я не знал, как это решить. Я понял, как найти самую длинную палиндромическую подпоследовательность, но не знаю, как реализовать отчетную соседнюю часть. Пожалуйста помоги. Псевдокод в порядке.

Answer 1

<Сильное> Золотое правило

Вот золотое правило динамического программирования.

Когда решения меньших подгруппов не могут быть объединены в решения для больших подгруппов из-за отсутствия информации, расширяют подгруппы добавления параметров , которые дают пропущенную информацию.

---

<Сильная> первая попытка

$ S $ - это последовательность $ n $ Письма или, $ s [0: n]. $

Пусть $ l [i] [j] $ - длина самой длинной палиндромической подпоследовательности $ s [i : j] $ . Легко выяснить базовые случаи и, увеличиваясь в $ i $ и / или уменьшение $ j $ , Отношения рецидива для $ l [i] [j] $ .

Теперь добавьте состояние даже длины. Пусть $ e [i] [j] $ быть длиной самой длинной длинной длиной палиндромической подпоследовательности $ s [i : j] $ . Мы можем выяснить базовые случаи и рецидивные отношения для $ E [i] [j] $ , аналогично тем, что $ L [i] [j] $ .

Теперь добавьте состояние различных соседних букв, то есть буква не может появиться дважды подряд, кроме буквы в центре. Пусть $ d [i] [j] $ - длина самых длинных длиннее длина отчетливой прилегающей пищевой палиндромической подпоследовательности $ S [i: j] $ . Как вы могли бы отметить, мы не можем выяснить рецидивовые отношения для $ D [I] [J] $ , поскольку расширение такая подпоследовательность дольше всего ввести повторное буквы.

Золотое правило приходит к спасению. Добавьте еще один параметр, который классифицирует письмо в конце самой длинной подпоследовательности, настолько, что мы можем определить, как правильно расширить эту подпоследовательность.

Пусть $ d [i] [j] [\ лямбда] $ - длина самой длинной длины долиной длины отчетливой палиндромической подпоследовательности $ S [I: J] $ Это заканчивается в письме $ \ lambda $ . То есть мы вычисляем $ D [I] [J] [\ Text {'} A \ Text {'}] $ , $ d [i] [j] [\ \ \ text {'} b \ text {'}] $ , $ d [i] [j] [\ \ \ \ Text {'} C \ Text {'}] $ , $ \ cdots $ , $ D [я ] [j] [\ \ text {'} z \ text {'}] $ .

.

• Окончательный ответ - больший из $ \ max_ \ lambda d [0] [n-1] [\ лямбда] $ и <класс span="Математический контейнер"> $ 0 $ .

• Предположим, первый $ \ text {'} A \ Text {'} $ в $ s $ at или после или после $ s [i] $ появляется на $ s [\ vec {i _ {\ text { '} A \ Text {'}}}] $ . Предположим, первый $ \ Text {'} A \ Text {'} $ в $ s $ появляется в $ s [\ overleftarrow {j _ {\ text {'} a \ text {'}}}] $ перед $ s [j] $ искал назад. $ \ vec {i _ {\ text {'} a \ text {'}}} $ или $ \ oveleftarrow {j_ {\ Text {'} A \ Text {'}}} $ устанавливается на $ - 1 $ Если $ \ text {'} A \ Text {'} $ не найдено соответственно. У нас есть, для $ j \ ge i + 2 $ ,

  $$ d [i] [j] [\ Text {'} A \ Text {'}]=begin {face} \ max (2, 2 + \ max _ {\ mu \ not=text {'} a \ text {'}} d [\ vec {i _ {\ text {'} a \ text {'}}} + 1] [\ udleftarrow {j _ {\ text {'} a \ text {'}}}] [\ mu]) & \ Text {Если} 0 \ le \ vec {i _ {\ text {'} a \ text {'} }} \ lt \ overleftarrow {j _ _ _ {\ text {'} a \ text {'}}}, \\ -1 и \ Text {В противном случае} \\ \ end {случаи} $$ где $ \ mu $ проходит через все строчные английские буквы.

• Базовый чехол - $$ d [i] [i] [\ Text {'} A \ Text {'}]= 0. $$

Обобщая $ \ text {'} A \ Text {'} $ Для переменной $ \ lambda $ , мы можем написать рецидивовое отношение и базовый случай для $ d [i] [j] [\ ad lambda] $ .

Обратите внимание, что при дополнительном информации, воплощенной в параметра $ \ lambda $ , легко вывести отношение рецидива.

Пока эта попытка успешна, мы можем сделать лучше.

---

<Сильная> Вторая попытка

Мы можем упростить подпункты.

Пусть $ f [i] [j] $ быть длиной самой длинной такой подпоследовательностью, которая запускается в $ S [i] $ и заканчивается на

Pan Class="Математический контейнер"> $ s [j] $ . Тогда у нас есть

$$ f [i] [j]=begin {Cass} \ max (2, 2 + \ max _ {\ mu \ not= s [i]} f [\ vec {i_ \ mu}] [\ udleftarrow {j_ \ mu}]) & \ text {Если} s [i]= S [j], \\ -1 и \ Text {В противном случае} \\ \ end {случаи} $$ где $ - 1 $ означает «не найден». Для всех строчных букв английского языка $ \ mu $ , $ s [\ vec {i_ \ mu}] $ является первым $ \ mu $ , который появляется после $ s [i] $ , а $ S [\ oveleftarrow {j_ \ mu}] $ - первый $ \ mu $ , который отображается до $ S [J] $ Назад. Если один из них не может быть найден, термин $ f [\ vec {i_ \ mu}] [\ udleftarrow {j_ \ mu}] $ игнорируется. .

Последний ответ - больший из $ \ max_ {i, j} f [i] [j] $ и 0.