Algorithm Cheat Sheet: Palindrome

A palindrome is a word, phrase, or other sequence that reads the same backward as forward. One interesting example is “A man, a plan, a canal, Panama!”. Such property of palindromes leads to interesting problems and solutions.

Palindrome determination

One typical problems about palindromes is to determine if a sequence of characters is a palindrome. For example, given an array \(a[0], a[1], \cdots, a[n]\), there can be different approaches.

Linear space

From the definition of palindromes, we generate a copy of the reversed sequence which basically reads the original sequence backward. We then compare the original sequence with the reversed version. That is, we check if it’s identical for the sequence of \(a[0], a[1], \cdots, a[n]\) and the sequence of \(a[n], a[n-1], \cdots, a[0]\).

The above approach can be optimized with less time. We divide the array into two sub-arrays with the equal size. We then reverse the second half and compare it with the first half. That is, we check if it’s identical for the sequence of \(a[0], a[1], \cdots, a[{n\over2}-1]\) and the sequence of \(a[n], a[n-1], \cdots, a[{n\over2}]\) (when \(n\) is even, or the sequence of \(a[n], a[n-1], \cdots, a[{n\over2}+1]\) when \(n\) is odd).

Constant space

It can be further optimized with less spaces by applying the comparison in-place. There can be two ways:

  1. Starting from both the head and tail of the array, we compare each pair of characters towards each other. That is, we first compare the pair of \(a[0]\) and \(a[n]\), and then the pair of \(a[1]\) and \(a[n-1]\), and so on until the pair of \(a[{n\over2}-1]\) and \(a[{n\over2}]\) (when \(n\) is even, or the pair of \(a[{n\over2}-1]\) and \(a[{n\over2}+1]\) when \(n\) is odd).

  2. Starting from the middle of the array, we compare each pair of characters towards the reversed directions. That is, we first compare the pair of \(a[{n\over2}-1]\) and \(a[{n\over2}]\) (when \(n\) is even, or the pair of \(a[{n\over2}-1]\) and \(a[{n\over2}+1]\) when \(n\) is odd), and then the next pair until the pair of \(a[1]\) and \(a[n-1]\).

Longest palindromic subsequence

Another interesting problem is to identify palindromes from a sequence of characters, for example, the longest palindromic subsequence. Based on to the above approaches of determining palindromes, we apply them accordingly.

Linear space

Recall that to determine if a sequence of characters is a palindrome, we compare it with its reversed version. Similarly, to identify the longest palindromic subsequence, we search the longest common subsequence between the original sequence and its reversed version. This can be solved with dynamic programming.

Note that there is a tricky difference between these two scenarios. By comparing a sequence and its reverse as a whole, we are verifying if the sequence is read the same backward as forward. This may not be always true for the longest common subsequence. We may end up with comparing two unrelated components. For example, given a sequence of aacdefcaa, its reverse is aacfedcaa. While it’s supposed to compare aac of the original sequence with caa of the reversed sequence, the algorithm naturally identifies aac as the longest common subsequence which apparently is not a palindrome.

We therefore further enforce the correct comparison. Given a sequence \(s\) and its reverse \(r\) with a size of \(n\), we apply dynamic programming and define an array \(a\) where \(a[x][y]\) indicates the longest common substring size between \(s\) and \(r\) ending in \(s[x-1]\) and \(r[y-1]\). The correct components for comparison are

$$ \begin{aligned} s[x-a[x][y]]\cdots s[x-1] ~~ \text{and} ~~ r[y-a[x][y]]\cdots r[y-1] & \text{, where} \\ & \\ (x-a[x][y]) + (y-1) = (x-1) + (y-a[x][y]) = n - 1 & \text{, that is} \\ & \\ x + y = a[x][y] + n & \end{aligned} $$

It doesn’t work by comparing the first half of the sequence with its second half, since the longest palindromic subsequence can appear at any location.

Constant space

Recall that there are two strategies of determining palindromes in-place:

  1. Starting from both the head and tail of the array, we compare each pair of characters towards each other.

  2. Starting from the middle of the array, we compare each pair of characters towards the reversed directions.

To find the longest palindromic subsequence, we traverse all possible subsequence cases and apply either strategy 1 or 2 to see if each case is a palindrome. The longest palindrome identified through the traversal becomes the result.

Interestingly, the time complexity will be different when choosing either strategy 1 or 2. While both strategies run in linear time on their own, traversing possible subsequence cases becomes different from each of them. For both strategies, we are traversing possible starting points. For strategy 1, this includes both the head and tail of a possible subsequence, resulting in \(O(n^2)\) time, whereas strategy 2 only involves the middle of a possible subsequence, which can be done in \(O(n)\) time. In fact, strategy 1 has redundancies. For example, given a sequence \(s\), if we know the subsequence of \(s[i]\cdots s[j]\) is not a palindrome, there is no need to check \(s[i-k]\cdots s[j+k]\).

Contents