Longest Palindromic Substring

How to find the longest palindromic substring in a string?

First we have to answer the question 'What is a palindrome?"

A palindrome is the same backwards and forwards.

For example, these are all palindromes

• "mom"
• "racecar"
• "taco cat"

      So when given a string (s) how do we determine if it is a palindrome? First off we need to determine if we will be considering just single words or if we will be considering cases that include spaces. For this situation we will be using single words to make it simpler.

      Some of the more common solutions include the 'brute force' method or check every substring to see if it is a palindrome. We could also do the expand from the center method which is more efficient than brute force. The best method is to use Manacher's Algorithm which is linear time and I recommend looking it up.

For this blog I am going to explain solving the problem using a matrix.

There are 3 variables to keep track of.

1. Index at where the palindrome starts (start)
2. Length of the palindrome (max)
3. Index offset (k)

def longest_palindrome(s)
   start = 0
   max = 0
   k = 2


end

      We will iterate through the string and when we run into matching letters (matrix[i][j]) where matrix[i+1][j-1] == true we can add another true to the table. To do this we need to initialize the matrix and set all matrix[i][i] = true because each character is a palindrome of size 1.

    for n in 0..s.length - 1
      matrix[n][n] = true
    end

	a	b	b	b	a	b	c
a	T
b		T
b			T
b				T
a					T
b						T
c							T

      We also need to go through and set matrix[i][i+1] to true if the characters match else the odd indicies can never be 'true' as you will see when we get to that part of the code.

    for m in 0..s.length - 1
      if (s[m] == s[m+1])
          matrix[m][m+1] = true
          start = m
          max = 1
      end
    end

	a	b	b	b	a	b	c
a	T
b		T	T
b			T	T
b				T
a					T
b						T
c							T

      Now if we go through the rest of the comparisons checking if the chars are the same and the matrix value is true to the bottom left ([i+1][j-1]) we will end up filling the matrix as such.

	a	b	b	b	a	b	c
a	T				T
b		T	T	T
b			T	T
b				T		T
a					T
b						T
c							T

    while (k < s.length)
        while (i < s.length - k)
            j = i + k
            if (s[j] == s[i] && !!matrix[i+1][j-1])
                matrix[i][j] = true

                if (k > max)
                    max = k
                    start = i
                end

            end
            i += 1
        end
        k += 1
        i = 0
    end

      We start with k = 2 since we already filled in the first two diagonals and then each time we increment k we set i = 0 and in the inner loop j = i + k (offset). At the end we can return the substring using the variables we saved. If we put it all together we have...

def longest_palindrome(s)
    start = 0
    max = 0

    if (s.length < 3)
        return "" if (s.length < 1)
        return s[0] if (s.length == 1)
        return s[0] == s[1] ? s : s[0]
    end

    matrix = Array.new(s.length) {Array.new(s.length)}

    for n in 0..s.length - 1
      matrix[n][n] = true
    end

    for m in 0..s.length - 1
      if (s[m] == s[m+1])
          matrix[m][m+1] = true
          start = m
          max = 1
      end
    end

    i = 0
    k = 2
    while (k < s.length)
        while (i < s.length - k)
            j = i + k
            if (s[j] == s[i] && !!matrix[i+1][j-1])
                matrix[i][j] = true

                if (k > max)
                    max = k
                    start = i
                end

            end
            i += 1
        end
        k += 1
        i = 0
    end

    return s[(start)..(start + max)]
end

And as always don't forget to add your base cases!

    if (s.length < 3)

        # empty string as input
        return "" if (s.length < 1)

        # string of length 1 should return the char
        return s[0] if (s.length == 1)

        # If there are two letters that are the same return the string else just the first char
        return s[0] == s[1] ? s : s[0]
    end

Please don't hesitate to give me feedback on my code! It's the only way we get better and I'm sure I have a long way to go =)