Understanding the top-down solution to the longest palindromic substring problem

To solve the longest palindromic substring problem using a top-down dynamic programming approach, we translate the recurrence relation into recursive functions and use memoization tables to store results of subproblems that have already been solved.

The top down solution

As with any top-down solution, there are recursive functions that solve subproblems and a calling function that initializes the required data structures and triggers the computation. However, the recurrence relation for the longest palindromic substring has two parts where one relies on the result from the other, and so we define two recursive functions that work together to solve the problem.

Why do we need two recursive functions instead of one?

The longest palindromic substring problem requires answering two distinct questions at each state:

Is this substring a palindrome? (a yes/no question handled by isPalindrome)What is the length of the longest palindromic substring within this range? (a numeric question handled by lps).

These are separated into two functions because combining them into one would force every lps call to re-explore the palindrome check from scratch, losing the benefit of memoization on the simpler sub-question.

The isPalindrome function

The function isPalindrome() takes as input a left index i, a right index j, a reference to the string s, and a reference to the 2D memoization array palindromeMemo. The function returns whether the substring s[i...j] is a palindrome.

Create a function isPalindrome to return if the substring s[i...j] is palindrome or not.

The palindromeMemo array has dimensions n × n and is initialized with -1 in the calling function, where -1 indicates that the state has not yet been computed. A value of 0 represents false, and 1 represents true.