Understanding the bottom up solution to the longest palindromic substring problem

To solve the longest palindromic substring problem using a bottom-up dynamic programming approach, we fill a table iteratively beginning from the smallest subproblems and building towards the final answer. As with any bottom-up solution, we process subproblems in an order that guarantees every result we depend on has already been computed and stored before we need it.

The bottom up solution

We solve the longest palindromic substring problem by first determining, for every pair of indices (i, j), whether the substring s[i...j] is a palindrome. We then scan these results to find the longest range that is a palindrome. To check whether a substring of a string s is a palindrome or not, we create a 2D boolean array isPalindrome of dimensions n × n, where isPalindrome[i][j] stores whether the substring from index i to j in the string s is a palindrome. It is initialized with all false values.