VBA – Longest Palindromic Subsequence Algorithm with Excel – GIF

After writing about the longest palindromic substring, now it is time to see the longest palindromic subsequence. What is the difference? Pretty much, if we take the word abracadabra:

  • the longest substring is ada in abracadabra
  • the longest subsequence is one of the following 3:
    • abadaba – in abracadabra
    • abaaaba – in abracadabra
    • abacada – in abracadabra

So, it is quite obvious that we have some kind of an interesting problem again, which could be solved with Excel. In order to solve it with a nice complexity, we are only going to find the lenght of the longest subsequence and display its starting and ending index. Thus for OPABRACADABRAK this would be the resulting picture:

So, let’s start with the algorithm:

This time, the yellow color is used only for visualisation and not into the calculations, as it was in the longest palindromic substring. The first loops parts of both algorithms are pretty much the same – they check the diagonal and simply write the values of 1 in there (in the palindromic substring it was a boolean value). Then a check for the length of 2 is made and if it was correct, then is written, otherwise 1:

Then the algorithms become a bit different. The current one is a typical greedy algorithm that does the following:

Compares values at the starting and the ending index of the researched string. If they are the same, then it increases the value from the left diagonal with 2. Otherwise it gives the maximal value of between the lower and the left cell:

The algorithm “in action” looks like this:

The GitHub code is here – https://github.com/Vitosh/VBA/blob/master/LongestPalindromicSubsequence.vb


Tagged with: , , , , ,