In this article, you will learn to analyze and resolve the longest palindromic substring problem by using a dynamic programming algorithm

A palindromic is a string that reads the same in both directions. A character itself is a palindrome

Problem

  • Given a string s

  • Write an algorithm to find the longest palindromic substring in s

Example

  • Input: "bananas". Expected output: "anana"

  • Input: "bb". Expected output: "bb"

  • Input: "a". Expected output: "a"

Approach 1: Brute Force

  • Find all substrings in the given string s

  • For each substring, check if it is the longest palindrome


  • Output
anana  
bb  
a  
  • Time complexity: O(n3)

  • Space complexity: O(1)

Approach 2: Dynamic Programming

  • Given a string bananas, we can say anana is a palindrome thanks to nan is a palindrome and the beginning character is the same with the ending character (a). And so on, nan is a palindrome due to a is a palindrome and the start letter equals to the end letter (n)

    So the optimal substructure is P(i,j) = (S(i) == S(j) && P(i+1,j-1)) with P(i,j) is a palindromic substring from index i to j

    Base cases: P(i,i) = true as a character itself is a palindrome, P(i,i+1) = (S(i) == S(i+1))

  • Bottom-up filling P[i][j] matrix value with i is an index of a character in the given string s, j is a length of possible palindrome substrings

    At each iteration, remember the substring's start index and max length to find the longest palindromic substring


  • Output
a  
bb  
ccc  
anana  
  • Time complexity: O(n2)

  • Space complexity: O(n2)