Longest Palindromic Substring

Approach: The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.

To generate odd length palindrome, Fix a centre and expand in both directions for longer palindromes, i.e. fix i (index) as center and two indices as i1 = i+1 and i2 = i-1

Compare i1 and i2 if equal then decrease i2 and increase i1 and find the maximum length.

Use a similar technique to find the even length palindrome.

Take two indices i1 = i and i2 = i-1 and compare characters at i1 and i2 and find the maximum length till all pair of compared characters are equal and store the maximum length.

        public string LongestPalindromicSubString(string str)

        {

            if(string.IsNullOrEmpty(str))

            {

                return string.Empty;

            }

            int maxLength = 1;

            int start = 0;

            for (int i = 1; i < str.Length; ++i)

            {

                // Find the longest even length palindrome with center points as i-1 and i.

                int low = i - 1;

                int high = i;

                while(low >= 0 && high < str.Length && str[low] == str[high])

                {

                    if (high - low + 1 > maxLength)

                    {

                        start = low;

                        maxLength = high - low + 1;

                    }

                    --low;

                    ++high;

                }

                // Find the longest odd length palindrome with center point as i

                low = i - 1;

                high = i + 1;

                while(low >= 0 && high <str.Length && str[low] == str[high])

                {

                    if (high - low + 1 > maxLength)

                    {

                        start = low;

                        maxLength = high - low + 1;

                    }

                    --low;

                    ++high;

                }

            }

            return str.Substring(start, maxLength);

        }

Complexity: O(n^2)