11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Joel David Hamkins Jan 23 '11 at 20:17
  • 1
    $\begingroup$ 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". $\endgroup$ – Matt Fayers Jan 23 '11 at 20:55
  • $\begingroup$ That is a better wording; thanks. I unconsciously took "longest common subsequence" as an unbreakable term of art. $\endgroup$ – Steve Jan 25 '11 at 20:23
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's a nice, clean proof. Thanks! $\endgroup$ – Steve Jan 25 '11 at 20:36
3
$\begingroup$

This problem is discussed and solved here .

$\endgroup$
  • 2
    $\begingroup$ Thanks for the reference. The problem is discussed there, but not solved. $\endgroup$ – Steve Jan 25 '11 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.