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.
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.
- Using recursion
- 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 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.
C | A | C | B | B | C | B | B | A | C | D | |
C | 1 | 1 | 3 | 3 | 3 | 4 | 4 | 5 | 5 | 5 | 5 |
A | 0 | 1 | 1 | 1 | 2 | 4 | 4 | 5 | 5 | 5 | 5 |
C | 0 | 0 | 1 | 1 | 2 | 4 | 4 | 5 | 5 | 5 | 5 |
B | 0 | 0 | 0 | 1 | 2 | 2 | 3 | 5 | 5 | 5 | 5 |
B | 0 | 0 | 0 | 0 | 1 | 1 | 3 | 3 | 3 | 3 | 3 |
C | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
B | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 2 | 2 | 2 |
B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
A | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
C | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
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 , 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!