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. If the input string is empty, its longest palindromic substring has length 0, and we handle this as a base case before any table allocation. 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.

The isPalindrome array has a size n x n and is initialized with false.

We initialize isPalindrome[i][i] to true for all 0 <= i < n since every single character is a palindrome, and this serves as the base case for the problem.

Why is only the diagonal initialized to true, and everything else to false?

The entries isPalindrome[i][i] correspond to substrings of length 1, which are always palindromes, so we set them to true upfront. All other entries correspond to substrings of length 2 or more whose palindrome status depends on the characters and possibly on inner substrings. These are computed during the main loops, and initializing them to false gives a safe default so that if an entry is never explicitly updated, it correctly reflects that the corresponding substring is not a palindrome.

isPalindrome[i][i] is set to true for 0 <= i < n as the base case.

We initialize a variable maxLength to 1 to keep track of the length of the longest palindromic substring found so far. Since every single character is a palindrome of length 1, this is a safe starting value for any non-empty string.