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*).



palindromic subsequences
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.








