C++ String Exercises: Length of the longest palindrome in a given string

C++ String: Exercise-20 with Solution

Write a C++ program to find the length of the longest palindrome in a given string (uppercase or lowercase letters).

From Wikipedia,
Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Note: Uppercase and lowercase letters are treated as distinct (case-sensitive)
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam, racecar.
In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome. For example, the longest palindromic substring of "bananas" is "anana". The longest palindromic substring is not guaranteed to be unique; for example, in the string "abracadabra", there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, "aca" and "ada". In some applications it may be necessary to return all maximal palindromic substrings (that is, all substrings that are themselves palindromes and cannot be extended to larger palindromic substrings) rather than returning only one substring or returning the maximum length of a palindromic substring.

Original string: adcdcdy
Length of the longest palindrome of the said string: 5
Original string: aaa
Length of the longest palindrome of the said string: 3
Original string: aa
Length of the longest palindrome of the said string: 2
Original string: abddddeeff
Length of the longest palindrome of the said string: 4
Original string: PYTHON
Length of the longest palindrome of the said string: 1

Sample Solution:

C++ Code:

#include <iostream> // Input/output stream library
#include <cstring> // C-style string manipulation library

using namespace std; // Using the standard namespace

// Function to find the length of the longest palindrome substring in a given string
int longest_Palindrome_length(string str) {
    int n = str.length(); // Length of the input string
    int substr_table[n][n]; // Table to store lengths of palindrome substrings

    // Fill the substr_table for substrings of length 1
    for (int i = 0; i < n; i++) {
        substr_table[i][i] = 1;
    }

    // Fill the substr_table for substrings of length 2
    for (int i = 0; i < n - 1; i++) {
        if (str[i] == str[i + 1]) {
            substr_table[i][i + 1] = 2;
        } else {
            substr_table[i][i + 1] = 0;
        }
    }

    // Fill the substr_table for substrings of length greater than 2
    for (int k = 3; k <= n; k++) {
        for (int i = 0; i < n - k + 1; i++) {
            int j = i + k - 1;
            if (str[i] == str[j] && substr_table[i + 1][j - 1] != 0) {
                substr_table[i][j] = substr_table[i + 1][j - 1] + 2;
            } else {
                substr_table[i][j] = 0;
            }
        }
    }

    // Find the maximum palindrome length in the substr_table
    int max_len = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (substr_table[i][j] > max_len) {
                max_len = substr_table[i][j];
            }
        }
    }

    return max_len; // Return the length of the longest palindrome
}

// Main function
int main() {
    // Test cases
    string str1 = "adcdcdy";
    cout << "Original string: " << str1;
    cout << "\nLength of the longest palindrome of the said string: " << longest_Palindrome_length(str1);

    str1 = "aaa";
    cout << "\n\nOriginal string: " << str1;
    cout << "\nLength of the longest palindrome of the said string: " << longest_Palindrome_length(str1);

    str1 = "aa";
    cout << "\n\nOriginal string: " << str1;
    cout << "\nLength of the longest palindrome of the said string: " << longest_Palindrome_length(str1);

    str1 = "abddddeeff";
    cout << "\n\nOriginal string: " << str1;
    cout << "\nLength of the longest palindrome of the said string: " << longest_Palindrome_length(str1);

    str1 = "PYTHON";
    cout << "\n\nOriginal string: " << str1;
    cout << "\nLength of the longest palindrome of the said string: " << longest_Palindrome_length(str1);

    return 0; // Return 0 to indicate successful completion
}

Sample Output:

Original string: adcdcdy
Length of the longest palindrome of the said string: 5
Original string: aaa
Length of the longest palindrome of the said string: 3
Original string: aa
Length of the longest palindrome of the said string: 2
Original string: abddddeeff
Length of the longest palindrome of the said string: 4
Original string: PYTHON
Length of the longest palindrome of the said string: 1

Flowchart:

C++ Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Reverse only the vowels of a given string.