Longest Palindromic Substring

Finding longest palindromic substring in a given string

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 of finding the longest palindromic substring in a given string using dynamic programming.
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’.

Longest Palindrome

Time complexity of finding the longest palindromic substring in a given string using dynamic programming : O(N^2), where N is the length of the string.


C++14 : Longest Palindromic Substring in a given string using dynamic programming

#include<iostream>
#include<string>
#include<cstring>

using namespace std;

// Below function finds the longest palindromic substring using dynamic programming
string LongestPalindromicSubstring (string str) {
    
    int N = str.size();
    int palindrome_begins_at = 0;
    int palindrome_length = 0;

    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;
        }
    }   
    
    // Loop from string length of size 3 upto the N 
    for (int len=3; len < N; len++) {
        for (int i=1; 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(){

    string str("TRSXYZZYXPOR");
    cout << "Longest Palindromic Substring: " << LongestPalindromicSubstring (str) << endl;
    str = "GAMEOFTHRONESALGOTREERTOGLAWHY";
    cout << "Longest Palindromic Substring: " << LongestPalindromicSubstring (str) << endl;
    str = "GOKAYAKING";
    cout << "Longest Palindromic Substring: " << LongestPalindromicSubstring (str) << endl;
    return 0;
};

Output showing the longest palindromic substring in a given string

Length of longest palindrome : 6
Longest Palindromic Substring: XYZZYX
Length of longest palindrome : 14
Longest Palindromic Substring: ALGOTREERTOGLA
Length of longest palindrome : 5
Longest Palindromic Substring: KAYAK

Copyright © 2019-2020, Algotree.org.
All rights reserved.