VBA – Longest Palindromic Substring Algorithm with Excel – GIF

The longest palindromic substring algorithm exists since 1975. It is different (and easier) than the longest palindromic subsequence. The idea of the substring is to return “anana”, if “bananazorro” is given. This is achieved with a 2 dimensional boolean array matrix and some strange checks like this one:

After writing the solution in C# (GitHub), I somehow still had problems to visualize in my head how exactly it worked. Thus, I have decided to write it in VBA and to visualize it with Excel, in order to catch it step-by-step. And after some time, I had this “Aha” moment, when I saw the display.

So, the idea of the algorithm is the following:

  • There are 3 cases:
    • Single letter palindrome (worst case)
    • Double letter palindrome
    • More than double letter palindrome
  • We write the word in a matrix nxin Excel and we color the diagonal letters:

  • Then we color the letters, which are doubled to the right of the diagonal:

  • And then the interesting part starts:
    • We only move to the right of the yellow diagonal line, completely ignoring the left side
    • We loop from 3 to the length of the word (as far as palindromes with size 1 or 2 are already checked in the previous steps)
    • We check for every position, whether the first and the last letter is the same and whether the left diagonal is loop
    • If true, we color in yellow as well. In the picture below, nnabann is considered palindrome, because the two n-s are equal and the to the right has a yellow predecessor in the lower left cell:

    • Once we find a cell which answers our conditions, we highlight it in yellow. We also write down the current length as a maximum one (because it is ascending from 3 to the length of the word.
    • At the end, we highlight the word, which is a palndrome, on a separate line:

It is really better to take a look at the code working a few times, in order to understand how it works. The letters in red in line 23 are the letters which are currently compared. The selected cell is the one which is compared to the initial diagonal line:

Here comes the VBA code (GitHub). The only requirement before pasting it in a module, is to name the worksheet with a codename tblMatrix :

That’s all folks! Sometimes VBA is better than C#, depending on what your target is. 🙂

Tagged with: , , , , , ,