Unlocking Maximum Palindromic Length With Powerful Recursion And Dynamic Programming

A substring is a sequence of characters which has been extracted from a larger string. For example, let’s consider the string “Hello World”. We can form the substring “Hello” by selecting the first five characters of the string. Let’s see the following another example.

The palindromic substring “BBCBB” is of length 5.

In order to calculate the length of a substring, we need to consider the difference between the starting and ending characters. If the length of the subset is equal to the difference between the start and end, then this subset can be considered to be a substring. This problem has multiple possible solutions.

  1. Using recursion
  2. Using Dynamic Programming

Before going to write the solutions for the different approaches, first, let’s find the formula for the recursion.

F(A, E, S) = 0  // When S > E
    = 1  // If S = E
    = maximum { 2 + F(A, E-1, S+1), F(A, E-1, S), F(A, E, S+1) } // If  characters at E & S are same (i.e., A[E] == A[S]) and E-S = 2 + F(A, E-1, S+1).
    = maximum { F(A, E-1, S+1), F(A, E-1, S), F(A, E, S+1) } // For all other cases.

// Where
A is an input array.
E is the ending point
S is the starting point.

Using Recursion

By using the above formula, we can write the recursion code, which is as showing below.

int longestPalindromicSubstrLenRec(char inp[], int len, int cur)
{
    if (cur > len)
    {
        return 0;
    }
    if (cur == len)
    {
        return 1;
    }
    int prevMax = longestPalindromicSubstrLenRec(inp, len - 1, cur + 1);
    if (inp[len] == inp[cur])
    {
        if (prevMax == len - cur - 1)
        {
            prevMax += 2;
        }
    }
    return max(longestPalindromicSubstrLenRec(inp, len - 1, cur),
               longestPalindromicSubstrLenRec(inp, len, cur + 1),
               prevMax);
}

This C++ program is used to calculate the length of the longest palindromic substring in an input string. It takes the input string, its length and an integer as parameters. The program recursively checks if the characters at the beginning and end of the input string are equal, and if they are, it adds two to the previous maximum length. Then it returns the maximum of three different recursive calls to the function. This recursive call calculates the length of the longest palindromic substring in the input string.

This recursion solution has a runtime complexity of O(3^N) which is exponential. To overcome this runtime complexity issue, we use dynamic programming. Let’s quickly jump into that solution.

Dynamic Programming approach

In this approach, we memorize the solution at each level and use it whenever we required it again. Let’s see the memorization table to solve this using Dynamic Programming.

CACBBCBBACD
C11333445555
A01112445555
C00112445555
B00012235555
B00001133333
C00000112222
B00000012222
B00000001111
A00000000111
C00000000011
D00000000001
NxN dynamic programming memory to find longest palindromic substring length.

We generated the above memorization matrix based on our formula. Value at the top-right edge gives us the longest palindromic substring length.

// Formula
dp[i][j] = 0 // if i < j
    = 1 // if i == j
    = maximum { 2+dp[i+1][j-1], dp[i+1][j], dp[i][j-1] } // If A[i] = A[j] and j-i = 2 + dp[i+1][j-1]
    = maximum { dp[i+1][j-1], dp[i+1][j], dp[i][j-1] } // For all other cases.

Let’s see the code for this approach.

int longestPalindromicSubstrLenDP(char inp[], int len)
{
    int dp[len][len];
    int i, j;
    int cntr = 0;
    for (i = 0; i < len; i++)
    {
        for (j = 0; j < len; j++)
        {
            if (i == j)
            {
                dp[i][j] = 1;
            }
            else
                dp[i][j] = 0;
        }
    }
    i = 0;
    j = 1;
    cntr = 1;
    while (1)
    {
        if (cntr == len && i == 0)
        {
            break;
        }
        int curr = dp[i + 1][j - 1];
        if (inp[i] == inp[j])
        {
            if (curr == (j - i - 1))
            {
                curr += 2;
            }
        }
        dp[i][j] = max(curr, dp[i + 1][j], dp[i][j - 1]);
        i++;
        j++;
        if (j >= len)
        {
            cntr++;
            i = 0;
            j = cntr;
        }
    }
    for (i = 0; i < len; i++)
    {
        for (j = 0; j < len; j++)
        {
            cout << dp[i][j] << "\t";
        }
        cout << endl;
    }
    return dp[0][len - 1];
}

This approach reduces a lot of runtime complexity when compared to recursion. This solution has a complexity of O(N*N), where N is the length of the string.

There are both recursion and dynamic programming approaches which can be used to solve the problem of finding the length of the longest palindromic substring. Additionally, there is an approach which has a complexity of O(N) which can be used to solve this problem. If anyone has any comments or suggestions on how to improve this topic, or how to help other readers, please let us know. We hope this has been a helpful learning experience!

See more:
http://rjp.b44.myftpupload.com/longest-common-subsequence-length-of-given-two-strings/
http://rjp.b44.myftpupload.com/count-of-all-subsets-with-given-sum-in-an-unsorted-integer-array/