Longest Even-Length Palindromic Subsequence (with distinct adjacent characters except for the center 2 letters)

Question

You are given a string S containing lowercase English characters. You need to find the length of the largest subsequence of S that satisfies the following pattern: X1,X2,X3...Xn,Xn,...X3,X2,X1 where Xi is some character of S. The only constraint is that no adjacent character should be the same except Xn, that is Xi != X(i+1) for all 1<=i< n.

Input: The string: S
Output: The integer: 2n
Constraint: 1<=|S|<=10^3

Sample input 1: "acdbdea"
Sample output 1: 4
Explanation: "adda" is the longest subsequence following the given pattern.

Sample input 2: "abbacdeedc"
Sample output 2: 6
Explanation: "cdeedc" is the longest subsequence following the given pattern.

Sample input 3: "taker"
Sample output 3: 0
Explanation: No subsequence follows the given pattern.

---

This question was asked in a coding interview and I didn't know how to solve it. I understood how to find the longest palindromic subsequence but don't know how to implement the distinct adjacent character part. Please help. Pseudocode is fine.

Answer 1

Golden Rule

Here is the golden rule of dynamic programming.

When solutions to smaller subproblems cannot be combined into solutions to larger subproblems because of missing information, extend the subproblems by adding parameters that give that missing information.

---

First attempt

$S$ is a sequence of $n$ letters or, $S[0:n].$

Let $L[i][j]$ be the length of the longest palindromic subsequence of $S[i:j]$. It is easy to figure out the base cases and, by increasing $i$ and/or decreasing $j$, the recurrence relations for $L[i][j]$.

Now add the condition of even length. Let $E[i][j]$ be the length of the longest even-length palindromic subsequence of $S[i:j]$. We can figure out the base cases and the recurrence relations for $E[i][j]$, similar to those of $L[i][j]$.

Now add the condition of distinct adjacent letters, i.e., no letter can appear twice in a row except the letter at the center. Let $D[i][j]$ be the length of the longest even-length distinct-adjacent-letter palindromic subsequence of $S[i:j]$. As you might have noted, we cannot figure out the recurrence relations for $D[i][j]$, since extending such a subsequence to a longer one might introduce repeated letters.

The golden rule comes to rescue. Add another parameter that classifies the letter at the end of the longest subsequence found so far, so that we can determine how to extend that subsequence properly.

Let $D[i][j][\lambda]$ be the length of the longest even-length distinct-adjacent-letter palindromic subsequence of $S[i:j]$ that ends in letter $\lambda$. That is, we will compute $D[i][j][\text{'}a\text{'}]$, $D[i][j][\text{'}b\text{'}]$, $D[i][j][\text{'}c\text{'}]$, $\cdots$, $D[i][j][\text{'}z\text{'}]$.

• The final answer is the larger of $\max_\lambda D[0][n-1][\lambda]$ and $0$.

• Suppose the first $\text{'}a\text{'}$ in $S$ at or after $S[i]$ appears at $S[\vec {i_{\text{'}a\text{'}}}]$. Suppose the first $\text{'}a\text{'}$ in $S$ appears at $S[\overleftarrow{j_{\text{'}a\text{'}}}]$ before $S[j]$ searched backwards. $\vec {i_{\text{'}a\text{'}}}$ or $\overleftarrow{j_{\text{'}a\text{'}}}$ is set to $-1$ if $\text{'}a\text{'}$ is not found respectively. We have, for $j\ge i+2$,

  $$D[i][j][\text{'}a\text{'}] = \begin{cases} \max(2, 2 + \max_{\mu\not=\text{'}a\text{'}}D[\vec {i_{\text{'}a\text{'}}}+1][\overleftarrow{j_{\text{'}a\text{'}}}][\mu])& \text{ if } 0\le \vec{i_{\text{'}a\text{'}}} \lt \overleftarrow{j_{\text{'}a\text{'}}},\\ -1 & \text{ otherwise,}\\ \end{cases} $$ where $\mu$ runs through all lowercase English letters.

• The base case is $$D[i][i][\text{'}a\text{'}] = 0.$$

Generalizing $\text{'}a\text{'}$ to variable $\lambda$, we can write the recurrence relation and base case for $D[i][j][\lambda]$.

Note that with the extra information embodied in the $\lambda$ parameter, it is easy to deduce the recurrence relation.

While this attempt is successful, we can do better.

---

Second attempt

We can simplify the subproblems.

Let $F[i][j]$ be the length of the longest such subsequence that starts at $S[i]$ and ends at $S[j]$. Then we have

$$F[i][j] = \begin{cases} \max(2, 2 + \max_{\mu\not=S[i]}F[\vec{i_\mu}][\overleftarrow{j_\mu}])&\text{ if } S[i] = S[j],\\ -1 & \text{ otherwise,}\\ \end{cases} $$ where $-1$ stands for "Not Found". For all lowercase English letter $\mu$, $S[\vec{i_\mu}]$ is the first $\mu$ that appears after $S[i]$, and $S[\overleftarrow{j_\mu}]$ is the first $\mu$ that appears before $S[j]$ searched backwards. If one of them cannot be found, the term $F[\vec {i_\mu}][\overleftarrow{j_\mu}]$ is ignored.

The final answer is the larger of $\max_{i, j} F[i][j]$ and 0.