C#: Get the longest Palindromic substring from a given string

C# Sharp String: Exercise-44 with Solution

Write a C# Sharp program to get the longest Palindromic substring from a given string.
From Wikipedia:
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".

Sample Solution:-

C# Sharp Code:

using System;
using System.Collections.Generic;

namespace exercises 
{
    class Program 
    {
        static void Main(string[] args) 
        {
            // Initialize a string variable and display the original string
            String str1;
            str1 = "aaaaaabbbbccc";
            Console.WriteLine("Original String: " + str1);

            // Display the length of the longest substring without repeating characters
            Console.WriteLine("Length of the longest substring without repeating characters of the said string:");
            Console.WriteLine(longest_Palindrome(str1));

            // Repeat the above steps for different strings
            str1 = "BDEFGAABEF";
            Console.WriteLine("Original String: " + str1);
            Console.WriteLine("Length of the longest substring without repeating characters of the said string:");
            Console.WriteLine(longest_Palindrome(str1));

            str1 = "Python";
            Console.WriteLine("Original String: " + str1);
            Console.WriteLine("Length of the longest substring without repeating characters of the said string:");
            Console.WriteLine(longest_Palindrome(str1));

            str1 = "Java";
            Console.WriteLine("Original String: " + str1);
            Console.WriteLine("Length of the longest substring without repeating characters of the said string:");
            Console.WriteLine(longest_Palindrome(str1));
        }

        // Method to find the length of the longest substring without repeating characters
        public static string longest_Palindrome(string s) 
        {
            // Convert the input string to a character array
            var chars_array = s.ToCharArray();

            // Initialize a boolean array to track palindrome substrings
            var bool_arr = new bool[chars_array.Length, chars_array.Length];
            int longest_start = 0;
            int max_length = 1;

            // Initialize the boolean array for single characters
            for (int i = 0; i < chars_array.Length; i++) 
            {
                bool_arr[i, i] = true;
            }

            // Check for palindrome substrings of length 2
            for (int i = 0; i < chars_array.Length - 1; i++) 
            {
                if (chars_array[i] == chars_array[i + 1]) 
                {
                    bool_arr[i, i + 1] = true;
                    longest_start = i;
                    max_length = 2;
                }
            }

            // Check for palindrome substrings of length greater than 2
            for (int length = 3; length <= chars_array.Length; length++) 
            {
                for (int i = 0; i < chars_array.Length - length + 1; i++) 
                {
                    int j = i + length - 1;
                    if (chars_array[i] == chars_array[j] && bool_arr[i + 1, j - 1]) 
                    {
                        bool_arr[i, j] = true;
                        if (max_length < (j - i)) 
                        {
                            max_length = j - i;
                            longest_start = i;
                        }
                    }
                }
            }

            // Return the substring with the longest length without repeating characters
            return s.Substring(longest_start, max_length);
        }
    }
}

Sample Output:

Original String: aaaaaabbbbccc
Length of the longest substring without repeating characters of the said string:
aaaaa
Original String: BDEFGAABEF
Length of the longest substring without repeating characters of the said string:
AA
Original String: Python
Length of the longest substring without repeating characters of the said string:
P
Original String: Java
Length of the longest substring without repeating characters of the said string:
av

Flowchart :

C# Sharp Code Editor:

Improve this sample solution and post your code through Disqus

Previous: Write a C# Sharp program to determine whether a string ends with a particular substring.
Next: Write a C# Sharp program to reverse a given string in uppercase.