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()

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;
};

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));
        }
    }
}

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