Longest Palindromic Substring
Finding the longest palindromic substring using dynamic programming
The idea of this algorithm is to mark a substring as palindrome if a) Characters at the beginning and end of substring match and b) Characters in between make a palindrome.
A two dimensional table is constructed to mark substring from position i till j as a palindrome. For palindrome_table [ i ] [ j ] to be true, in between substring i.e substring from ( i + 1 ) and ( j - 1 ) should also be a palindrome.
This dynamic programming algorithm takes a bottom-up approach i.e we find out the palindromes from length 1 all the way till the length of the given string.
Example:
Base Case(s):
- Every single character makes a palindrome.
- Same ajacent characters make a palindrome of length 2.
- For substrings of size 3 upto the length of the string, Mark substring from i till j as palindrome i.e palindrome_table [ i ] [ j ] = true, if string [ i + 1 ] [ j - 1 ] is palindrome and character at the beginning i.e [ i ] matches character at the end i.e [ j ] .
Time complexity : O ( N 2 ), where N is the length of the string.
Implementation of finding the longest palindromic substring
# Below function finds the longest palindromic substring using dynamic programming
# Note: If there are 2 or more palindromic substrings of the same length in the given string
# the first palindromic string gets printed.
def LongestPalindrome (string):
N = len(string)
palindrome_begins_at = 0
palindrome_length = 1
# Create 2 dimensional boolean table
ispalindrome_table = [False] * N
for i in range (N):
ispalindrome_table[i] = [False] * N
# Base case: Every character in a string is a palindrome.
for i in range (0,N):
for j in range (0,N):
if i == j:
ispalindrome_table[i][j] = True
# Base case: Same adjacent characters in a string make a palindrome.
for i in range (N-1):
if (string[i] == string[i+1]):
ispalindrome_table[i][i+1] = True
palindrome_begins_at = i
palindrome_length = 2
# Loop from string length of size 3 upto the N
for length in range (3, N+1):
for i in range (0, N - length + 1):
j = i + length - 1
if (string[i] == string[j] and ispalindrome_table[i+1][j-1] == 1):
ispalindrome_table[i][j] = True
if (length > palindrome_length):
palindrome_begins_at = i
palindrome_length = length
print("Length of the longest palindrome : " + str(palindrome_length))
return string[palindrome_begins_at : palindrome_begins_at + palindrome_length]
def main():
string_list = ["ABC", "ABA", "ABBA", "ABBC", "KK", "AAAAAAAAXABCDDCBA", "TRSXYZZYXPOR",
"GAMEOFTHRONESALGOTREERTOGLAWHY", "GOKAYAKING"]
for string in (string_list):
print("\nString : " + string)
print("Longest Palindromic Substring: " + LongestPalindrome (string))
if __name__ == "__main__":
main()
Output
String : ABC
Length of the longest palindrome : 1
Longest Palindromic Substring: A
String : ABA
Length of the longest palindrome : 3
Longest Palindromic Substring: ABA
String : ABBA
Length of the longest palindrome : 4
Longest Palindromic Substring: ABBA
String : ABBC
Length of the longest palindrome : 2
Longest Palindromic Substring: BB
String : KK
Length of the longest palindrome : 2
Longest Palindromic Substring: KK
String : AAAAAAAAXABCDDCBA
Length of the longest palindrome : 8
Longest Palindromic Substring: AAAAAAAA
String : TRSXYZZYXPOR
Length of the longest palindrome : 6
Longest Palindromic Substring: XYZZYX
String : GAMEOFTHRONESALGOTREERTOGLAWHY
Length of the longest palindrome : 14
Longest Palindromic Substring: ALGOTREERTOGLA
String : GOKAYAKING
Length of the longest palindrome : 5
Longest Palindromic Substring: KAYAK
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
// Below function finds the longest palindromic substring using dynamic programming.
// Note: If there are 2 or more palindromic substrings of the same length in the given string
// the first palindromic string gets printed.
string LongestPalindrome (const string& str) {
int N = str.size();
int palindrome_begins_at = 0;
int palindrome_length = 1;
bool ispalindrome_table[N][N];
memset(ispalindrome_table, false, sizeof(bool)*N*N);
// Base case: Every character in a string is a palindrome.
for (int i=0; i<N; i++) {
ispalindrome_table[i][i] = true;
}
// Base case: Same adjacent characters in a string make a palindrome.
for (int i=0; i<N-1; i++) {
if (str.at(i) == str.at(i+1)) {
ispalindrome_table[i][i+1] = true;
palindrome_begins_at = i;
palindrome_length = 2;
}
}
// Loop from string length of size 3 upto the N
for (int len=3; len <= N; len++) {
for (int i=0; i < N-len+1; i++) {
int j = i+len-1;
if (str[i] == str[j] and ispalindrome_table[i+1][j-1] == true) {
ispalindrome_table[i][j] = true;
if (len > palindrome_length) {
palindrome_begins_at = i;
palindrome_length = len;
}
}
}
}
cout << "Length of the longest palindrome : " << palindrome_length << endl;
return str.substr(palindrome_begins_at, palindrome_length);
};
int main() {
vector<string> vec = {"ABC", "ABA", "LPPLT", "RRT", "OO", "AAAAAAAAXABCDDCBA", "TRSXYZZYXPOR",
"GAMEOFTHRONESALGOTREERTOGLAWHY", "GOKAYAKING"};
for(const auto& str : vec) {
cout << "String : " << str << endl;
string palindrome = LongestPalindrome (str);
cout << "Longest Palindromic Substring: " << palindrome << "\n\n";
}
return 0;
};
Output
String : ABC
Length of the longest palindrome : 1
Longest Palindromic Substring: A
String : ABA
Length of the longest palindrome : 3
Longest Palindromic Substring: ABA
String : LPPLT
Length of the longest palindrome : 4
Longest Palindromic Substring: LPPL
String : RRT
Length of the longest palindrome : 2
Longest Palindromic Substring: RR
String : OO
Length of the longest palindrome : 2
Longest Palindromic Substring: OO
String : AAAAAAAAXABCDDCBA
Length of the longest palindrome : 8
Longest Palindromic Substring: AAAAAAAA
String : TRSXYZZYXPOR
Length of the longest palindrome : 6
Longest Palindromic Substring: XYZZYX
String : GAMEOFTHRONESALGOTREERTOGLAWHY
Length of the longest palindrome : 14
Longest Palindromic Substring: ALGOTREERTOGLA
String : GOKAYAKING
Length of the longest palindrome : 5
Longest Palindromic Substring: KAYAK
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
class Palindrome {
// Below function finds the longest palindromic substring using dynamic programming
// Note: If there are 2 or more palindromic substrings of the same length in the given string
// the first palindromic string gets printed.
static String LongestPalindrome (String str) {
int N = str.length();
int palindrome_begins_at = 0;
int palindrome_length = 1;
boolean ispalindrome_table[][] = new boolean[N][N];
// Base case: Every character in a string is a palindrome.
for (int i=0; i<N; i++) {
ispalindrome_table[i][i] = true;
}
// Base case: Same adjacent characters in a string make a palindrome.
for (int i=0; i<N-1; i++) {
if (str.charAt(i) == str.charAt(i+1)) {
ispalindrome_table[i][i+1] = true;
palindrome_begins_at = i;
palindrome_length = 2;
}
}
// Loop from string length of size 3 upto the N
for (int len=3; len <= N; len++) {
for (int i=0; i < N-len+1; i++) {
int j = i+len-1;
if (str.charAt(i) == str.charAt(j) && ispalindrome_table[i+1][j-1] == true) {
ispalindrome_table[i][j] = true;
if (len > palindrome_length) {
palindrome_begins_at = i;
palindrome_length = len;
}
}
}
}
System.out.println("Length of the longest palindrome : " + palindrome_length);
return str.substring(palindrome_begins_at, palindrome_begins_at + palindrome_length);
}
public static void main (String[] args) {
List<String> string_list = Arrays.asList("ABC", "ABA", "RRT", "ROOP", "MM", "AAAAAAAAXABCDDCBA", "TRSXYZZYXPOR",
"GAMEOFTHRONESALGOTREERTOGLAWHY", "GOKAYAKING");
for (String str : string_list) {
System.out.println("\nString : " + str);
System.out.println("Longest Palindromic Substring: " + LongestPalindrome (str));
}
}
}
Output
String : ABC
Length of the longest palindrome : 1
Longest Palindromic Substring: A
String : ABA
Length of the longest palindrome : 3
Longest Palindromic Substring: ABA
String : RRT
Length of the longest palindrome : 2
Longest Palindromic Substring: RR
String : ROOP
Length of the longest palindrome : 2
Longest Palindromic Substring: OO
String : MM
Length of the longest palindrome : 2
Longest Palindromic Substring: MM
String : AAAAAAAAXABCDDCBA
Length of the longest palindrome : 8
Longest Palindromic Substring: AAAAAAAA
String : TRSXYZZYXPOR
Length of the longest palindrome : 6
Longest Palindromic Substring: XYZZYX
String : GAMEOFTHRONESALGOTREERTOGLAWHY
Length of the longest palindrome : 14
Longest Palindromic Substring: ALGOTREERTOGLA
String : GOKAYAKING
Length of the longest palindrome : 5
Longest Palindromic Substring: KAYAK