# palindromic subsequences

I'd like any insight or references to the following two conjectures (see the glossary below for definitions):

Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and its reversal $x^R$ that is a palindrome.

Conjecture 2: For any string $x$ over a two-letter alphabet, all longest common subsequences of $x$ and $x^R$ are palindromes.

Conjecture 2 is not true for strings over a three-letter alphabet, a counterexample being $abacbab$, which has $abcab$ and $bacba$ as longest common subsequences.

Glossary:

A string (or word) is any finite sequence of objects ("letters") drawn from some finite set (the "alphabet").

For any string $x = x_1x_2\cdots x_{n-1}x_n$ of length $n$, the reversal of $x$ is $x^R := x_nx_{n-1}\cdots x_2x_1$.

A string $x$ is a palindrome if $x = x^R$.

A string $x$ is a subsequence of a string $y$ if $x$ results from $y$ by removing zero or more letters (in arbitrary locations, closing up any gaps that result).

A longest common subsequence (LCS) of two strings $x$ and $y$ is a string $z$ that is a subsequence of both $x$ and $y$ such that no string longer than $z$ has this property. Generally, $x$ and $y$ may have several different LCSs. There is a well-known algorithm to find an LCS of two given strings that runs in quadratic time (see e.g., Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms).

-
In Conjecture 1, I think you mean to say "which is a palindrome" rather than "that is a palindrome", since you don't want this part of the clause to delimit the prior "longest" property. That is, I think you are conjecturing that there is a longest common subsequence, which moreover has the additional property of being a palindrome. – Joel David Hamkins Jan 23 '11 at 20:17
Better still, since there is trivially a longest common subsequence, say "among the longest common subsequences, there is at least one which is a palindrome". – Matt Fayers Jan 23 '11 at 20:55
That is a better wording; thanks. I unconsciously took "longest common subsequence" as an unbreakable term of art. – Steve Jan 25 '11 at 20:23

## 2 Answers

OK. Having failed to make a counterexample, let's attempt a proof of Conjecture 1.

Suppose that $x$ and $x^R$ have a common subsequence $s$ of length $k$. This means that there are $n_1 < n_2 < \ldots < n_k$ and $m_1 > m_2 > \ldots > m_k$ such that $x_{n_i}=x_{m_i}$.

Now look for the place where they cross: $j=\max\{i\colon n_i\le m_i\}$. Terms prior to $j$ are paired with things in front of them; terms after are paired with things behind them. The $j$ term could be paired either with itself or something in front. By reversing the sequence if necessary you can assume that $j\ge k/2$. Further if $j=k/2$ you can assume that $n_j < m_j$ as otherwise by reversing the sequence you get $j=k/2+1$.

Now you can construct a palindromic subsequence: $x_{n_1}x_{n_2}\ldots x_{n_{k/2}}x_{m_{k/2}}x_{m_{k/2-1}}\ldots x_{m_1}$ in the case where $k$ is even or $x_{n_1}x_{n_2}\ldots x_{n_{(k+1)/2}}x_{m_{(k-1)/2}}\ldots x_{m_1}$ in the case where $k$ is odd.

-
That's a nice, clean proof. Thanks! – Steve Jan 25 '11 at 20:36

This problem is discussed and solved here .

-
Thanks for the reference. The problem is discussed there, but not solved. – Steve Jan 25 '11 at 20:17