Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
That's a nice, clean proof. Thanks! –  Steve Jan 25 '11 at 20:36
add comment

This problem is discussed and solved here .

share|improve this answer
    
Thanks for the reference. The problem is discussed there, but not solved. –  Steve Jan 25 '11 at 20:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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