Longest Palindromic Substring using Dynamic Programming
Last Updated :
13 Sep, 2023
Given a string, find the longest substring which is a palindrome.
Examples:
Input: Given string :"forgeeksskeegfor",
Output: "geeksskeeg".
Input: Given string :"Geeks",
Output: "ee".
BRUTE APPROACH: (TABULATION METHOD)
Intuition:
- We create a 2-D array to fill the array with appropriate steps.
- We fill the matrix using the gap method where we fill the matrix in a diagonal way .
- At every step ,we check if the substring generated has meet the condition of palindrome or not.
- At every step, we keep a counter variable to store the max length of the palindrome string achieved so far.
- Atlast we return the ans.
Implementation:
C++
#include <iostream>
using namespace std;
string longestPalin(string s) {
int count = -1;
string ans = "";
int n = s.length();
bool dp[n][n];
for (int g = 0; g < n; g++) {
for (int i = 0, j = g; j < n; i++, j++) {
if (g == 0) {
dp[i][j] = true;
} else if (g == 1) {
dp[i][j] = (s[i] == s[j]);
} else {
dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
}
if (dp[i][j] && count < j - i + 1) {
ans = s.substr(i, j - i + 1);
count = ans.length();
}
}
}
return ans;
}
int main() {
string str = "forgeeksskeegfor";
cout << longestPalin(str) << endl;
return 0;
}
|
Java
class LongestPalindrome {
static String longestPalin(String s) {
int count = -1;
String ans = "";
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int g = 0; g < n; g++) {
for (int i = 0, j = g; j < n; i++, j++) {
if (g == 0) {
dp[i][j] = true;
} else if (g == 1) {
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else {
dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
}
if (dp[i][j] && count < s.substring(i, j + 1).length()) {
ans = s.substring(i, j + 1);
count = ans.length();
}
}
}
return ans;
}
public static void main(String[] args) {
String str = "forgeeksskeegfor";
System.out.println(longestPalin(str));
}
}
|
Python3
def longest_palin(s):
count = -1
ans = ""
n = len(s)
dp = [[False] * n for _ in range(n)]
for g in range(n):
for i in range(n - g):
j = i + g
if g == 0:
dp[i][j] = True
elif g == 1:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (s[i] == s[j] and dp[i + 1][j - 1])
if dp[i][j] and count < j - i + 1:
ans = s[i:j + 1]
count = len(ans)
return ans
str = "forgeeksskeegfor"
print(longest_palin(str))
|
C#
using System;
public class LongestPalindrome
{
public static string LongestPalin(string s)
{
int count = -1;
string ans = "";
int n = s.Length;
bool[,] dp = new bool[n, n];
for (int g = 0; g < n; g++)
{
for (int i = 0, j = g; j < n; i++, j++)
{
if (g == 0)
{
dp[i, j] = true;
}
else if (g == 1)
{
dp[i, j] = (s[i] == s[j]);
}
else
{
dp[i, j] = (s[i] == s[j] && dp[i + 1, j - 1]);
}
if (dp[i, j] && count < j - i + 1)
{
ans = s.Substring(i, j - i + 1);
count = ans.Length;
}
}
}
return ans;
}
public static void Main(string[] args)
{
string str = "forgeeksskeegfor";
Console.WriteLine(LongestPalin(str));
}
}
|
Javascript
function longestPalin(s) {
let count = -1;
let ans = "";
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(false));
for (let g = 0; g < n; g++) {
for (let i = 0, j = g; j < n; i++, j++) {
if (g === 0) {
dp[i][j] = true;
} else if (g === 1) {
dp[i][j] = s[i] === s[j];
} else {
dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
}
if (dp[i][j] && count < j - i + 1) {
ans = s.substring(i, j + 1);
count = ans.length;
}
}
}
return ans;
}
const str = "forgeeksskeegfor";
console.log(longestPalin(str));
|
Time Complexity: O(N^2), where N is the length of string
Space Complexity: O(N^2) since have created a 2-D array.
Common mistake: Wrong Approach:
Some people will be tempted to come up with a O(n) time complexity quick solution, which is unfortunately flawed (however can be corrected easily):
(i)Reverse S and store it in S’.
(ii)Find the longest common substring between S and S’ which must also be the longest palindromic substring.
This seemed to work, let’s see some examples below.
For example, S = “caba” then S’ = “abac”.
The longest common substring between S and S’ is “aba”, which is the answer.
Let’s try another example: S = “abacdfgdcaba” then S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.
Correct Approach:
We could see that the longest common substring method fails when there exists a reversed copy of a non-palindromic substring in some other part of S. To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate. This gives us an O(n^2) Dynamic Programming solution which uses O(n^2) space (which could be improved to use O(n) space).
Dynamic programming Approach: Dynamic programming solution is already discussed here in the previous post. The time complexity of the Dynamic Programming based solution is O(n^2) and it requires O(n^2) extra space. We can find the longest palindrome substring( LPS ) in (n^2) time with O(1) extra space.
The algorithm below is very simple and easy to understand. The idea is to Fix a center and expand in both directions for longer palindromes and keep track of the longest palindrome seen so far.
ALGO:
- Maintain a variable ‘ maxLength = 1 ‘ (for storing LPS length) and ‘ start =0 ‘ (for storing starting index of LPS ).
- The idea is very simple, we will traverse through the entire string with i=0 to i<(length of string).
- while traversing, initialize ‘low‘ and ‘high‘ pointer such that low= i-1 and high= i+1.
- keep incrementing ‘high’ until str[high]==str[i] .
- similarly keep decrementing ‘low’ until str[low]==str[i].
- finally we will keep incrementing ‘high’ and decrementing ‘low’ until str[low]==str[high].
- calculate length=high-low-1, if length > maxLength then maxLength = length and start = low+1 .
- Print the LPS and return maxLength.
C++
#include <bits/stdc++.h>
using namespace std;
int longestPalSubstr(string str)
{
int n = str.size();
if (n < 2)
return n;
int maxLength = 1, start = 0;
int low, high;
for (int i = 0; i < n; i++) {
low = i - 1;
high = i + 1;
while (high < n
&& str[high] == str[i])
high++;
while (low >= 0
&& str[low] == str[i])
low--;
while (low >= 0 && high < n
&& str[low] == str[high]) {
low--;
high++;
}
int length = high - low - 1;
if (maxLength < length) {
maxLength = length;
start = low + 1;
}
}
cout << "Longest palindrome substring is: ";
cout << str.substr(start, maxLength);
return maxLength;
}
int main()
{
string str = "forgeeksskeegfor";
cout << "\nLength is: " << longestPalSubstr(str)
<< endl;
return 0;
}
|
C
#include <stdio.h>
#include <string.h>
void printSubStr(char* str, int low, int high)
{
for (int i = low; i <= high; ++i)
printf("%c", str[i]);
}
int longestPalSubstr(char* str)
{
int n = strlen(str);
if (n < 2)
return n;
int maxLength = 1, start = 0;
int low, high;
for (int i = 0; i < n; i++) {
low = i - 1;
high = i + 1;
while (high < n
&& str[high] == str[i])
high++;
while (low >= 0
&& str[low] == str[i])
low--;
while (low >= 0 && high < n
&& str[low] == str[high]) {
low--;
high++;
}
int length = high - low - 1;
if (maxLength < length) {
maxLength = length;
start = low + 1;
}
}
printf("Longest palindrome substring is: ");
printSubStr(str, start, start + maxLength - 1);
return maxLength;
}
int main()
{
char str[] = "forgeeksskeegfor";
printf("\nLength is: %d", longestPalSubstr(str));
return 0;
}
|
Java
public class LongestPalinSubstring {
static int longestPalSubstr(String str)
{
int n = str.length();
if (n < 2)
return n;
int maxLength = 1,start=0;
int low, high;
for (int i = 0; i < n; i++) {
low = i - 1;
high = i + 1;
while ( high < n && str.charAt(high) == str.charAt(i))
high++;
while ( low >= 0 && str.charAt(low) == str.charAt(i))
low--;
while (low >= 0 && high < n && str.charAt(low) == str.charAt(high) ){
low--;
high++;
}
int length = high - low - 1;
if (maxLength < length){
maxLength = length;
start=low+1;
}
}
System.out.print("Longest palindrome substring is: ");
System.out.println(str.substring(start, start + maxLength ));
return maxLength;
}
public static void main(String[] args)
{
String str = "forgeeksskeegfor";
System.out.println("Length is: "
+ longestPalSubstr(str));
}
}
|
Python3
def longestPalSubstr(string):
n = len(string)
if (n < 2):
return n
start=0
maxLength = 1
for i in range(n):
low = i - 1
high = i + 1
while (high < n and string[high] == string[i] ):
high=high+1
while (low >= 0 and string[low] == string[i] ):
low=low-1
while (low >= 0 and high < n and string[low] == string[high] ):
low=low-1
high=high+1
length = high - low - 1
if (maxLength < length):
maxLength = length
start=low+1
print ("Longest palindrome substring is:",end=" ")
print (string[start:start + maxLength])
return maxLength
string = ("forgeeksskeegfor")
print("Length is: " + str(longestPalSubstr(string)))
|
C#
using System;
class GFG {
public static int longestPalSubstr(string str)
{
int n = str.Length;
if (n < 2)
return n;
int maxLength = 1,start=0;
int low, high;
for (int i = 0; i < n; i++) {
low = i - 1;
high = i + 1;
while ( high < n && str[high] == str[i] )
high++;
while ( low >= 0 && str[low] == str[i])
low--;
while (low >= 0 && high < n && str[low] == str[high] ){
low--;
high++;
}
int length = high - low - 1;
if (maxLength < length){
maxLength = length;
start=low+1;
}
}
Console.Write("Longest palindrome substring is: ");
Console.WriteLine(str.Substring(start, maxLength));
return maxLength;
}
public static void Main(string[] args)
{
string str = "forgeeksskeegfor";
Console.WriteLine("Length is: "
+ longestPalSubstr(str));
}
}
|
Javascript
<script>
function longestPalSubstr(str)
{
let n = str.length;
if (n < 2)
return n;
let maxLength = 1,start=0;
let low, high;
for (let i = 0; i < n; i++) {
low = i - 1;
high = i + 1;
while ( high < n && str[high] == str[i])
high++;
while ( low >= 0 && str[low] == str[i])
low--;
while (low >= 0 && high < n && str[low] == str[high]){
low--;
high++;
}
let length = high - low - 1;
if (maxLength < length) {
maxLength = length;
start=low+1;
}
}
document.write("Longest palindrome substring is: ");
document.write(str.substring(start,maxLength+start));
return maxLength;
}
let str = "forgeeksskeegfor";
document.write("</br>","Length is: " + longestPalSubstr(str),"</br>");
</script>
|
Output
Longest palindrome substring is: geeksskeeg
Length is: 10
Complexity Analysis:
- Time complexity: O(n^2), where n is the length of the input string.
Outer Loop that traverses through the entire string, and Inner Loop that is used to expand from i .
- Auxiliary Space: O(1).
No extra space is needed.
The Above approach is a cleaner way.
The function implementation to print the LPS and return the maxLength is given below:
C++
#include <bits/stdc++.h>
using namespace std;
int maxLength;
string res;
void cSubUtil(string& s, int l, int r)
{
while (l >= 0 && r < s.length() && s[l] == s[r]) {
l--;
r++;
}
if (r - l - 1 >= maxLength) {
res = s.substr(l + 1, r - l - 1);
maxLength = r - l - 1;
}
return;
}
int longestPalSubstr(string str)
{
res = "";
maxLength = 1;
for (int i = 0; i < str.length(); i++) {
cSubUtil(str, i, i);
cSubUtil(str, i, i + 1);
}
cout << "Longest palindrome substring is: ";
cout << res << "\n";
return maxLength;
}
int main()
{
string str = "forgeeksskeegfor";
cout << "\nLength is: " << longestPalSubstr(str)
<< endl;
return 0;
}
|
Java
public class LongestPalinSubstring {
static int maxLength;
static String res;
static void cSubUtil(String s, int l, int r)
{
while (l >= 0 && r < s.length()
&& s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
if (r - l - 1 >= maxLength) {
res = s.substring(l + 1, r);
maxLength = r - l - 1;
}
return;
}
static int longestPalSubstr(String str)
{
res = "";
maxLength = 1;
for (int i = 0; i < str.length(); i++) {
cSubUtil(str, i, i);
cSubUtil(str, i, i + 1);
}
System.out.print(
"Longest palindrome substring is: ");
System.out.println(res);
return maxLength;
}
public static void main(String[] args)
{
String str = "forgeeksskeegfor";
System.out.println("Length is: "
+ longestPalSubstr(str));
}
}
|
Python3
class LongestPalinSubstring :
maxLength = 0
res = None
@staticmethod
def cSubUtil( s, l, r) :
while (l >= 0 and r < len(s) and s[l] == s[r]) :
l -= 1
r += 1
if (r - l - 1 >= LongestPalinSubstring.maxLength) :
LongestPalinSubstring.res = s[l + 1:r]
LongestPalinSubstring.maxLength = r - l - 1
return
@staticmethod
def longestPalSubstr( str) :
LongestPalinSubstring.res = ""
LongestPalinSubstring.maxLength = 1
i = 0
while (i < len(str)) :
LongestPalinSubstring.cSubUtil(str, i, i)
LongestPalinSubstring.cSubUtil(str, i, i + 1)
i += 1
print("Longest palindrome substring is: ", end ="")
print(LongestPalinSubstring.res)
return LongestPalinSubstring.maxLength
@staticmethod
def main( args) :
str1 = "forgeeksskeegfor"
print("Length is: " + str(LongestPalinSubstring.longestPalSubstr(str1)))
if __name__=="__main__":
LongestPalinSubstring.main([])
|
C#
using System;
class GFG {
static int maxLength;
static string res;
public static void cSubUtil(string s, int l, int r)
{
while (l >= 0 && r < s.Length && s[l] == s[r]) {
l--;
r++;
}
if (r - l - 1 >= maxLength) {
res = s.Substring(l + 1, r - l - 1);
maxLength = r - l - 1;
}
return;
}
public static int longestPalSubstr(string str)
{
res = "";
maxLength = 1;
for (int i = 0; i < str.Length; i++) {
cSubUtil(str, i, i);
cSubUtil(str, i, i + 1);
}
Console.Write("Longest palindrome substring is: ");
Console.WriteLine(res);
return maxLength;
}
public static void Main(string[] args)
{
string str = "forgeeksskeegfor";
Console.WriteLine("Length is: "
+ longestPalSubstr(str));
}
}
|
Javascript
let maxLength = 0;
let res = "";
function cSubUtil(s, l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) {
l--;
r++;
}
if (r - l - 1 >= maxLength) {
res = s.substring(l + 1, r);
maxLength = r - l - 1;
}
return;
}
function longestPalSubstr(str) {
res = "";
maxLength = 1;
for (let i = 0; i < str.length; i++) {
cSubUtil(str, i, i);
cSubUtil(str, i, i + 1);
}
console.log("Longest palindrome substring is: " + res);
return maxLength;
}
let str = "forgeeksskeegfor";
console.log("\nLength is: " + longestPalSubstr(str));
|
Output
Longest palindrome substring is: geeksskeeg
Length is: 10