How to find the longest palindromic substring

Given a string, return the longest palindromic substring of a given string

A palindrome is a string that reads the same backward as forward. For instance, level, baab

 

Example 1

Input:   abac

Output:  aba

Example 2

Input:   acdbba

Output:  bb

As usual, in the beginning, we need to understand the problem. We already know what a palindrome is and how to check if a string is a palindrome. The last unknown is - substring.

A substring is a subset or part of another string or a contiguous sequence of characters within a string.

Now we know what we need to find and can start thinking about the approach. Let's see several palindrome examples, maybe it will help to find out the approach.

bab <- one character in the middle
aaa
bbaabb <- two characters in the middle
baab

If we look carefully, it's easy to notice. A palindrome has one or two characters in the middle. We can use this knowledge.

Approach

To find the longest palindromic substring, we can try to use each character and pair as a middle of a palindrome and try to expand the palindrome. Let's see the approach step by step.

1. Take the first character as a middle of a palindrome
2. Try to add one character to the left and one to the right.
   • if, after adding characters, we still have a palindrome => we can continue to add characters
   • if was not able to add characters or the substring is not a palindrome => try to use another character as a middle of a palindrome

We need to repeat this for each character and each pair of characters.

Code

    public string LongestPalindromicSubstring(string text)
    {
        if (string.IsNullOrEmpty(text))
        {
            return string.Empty;
        }

        string[] result = new string[1];
        result[0] = string.Empty;

        for (int i = 0; i < text.Length; i++)
        {
            // try each character as a middle of a palindrome
            CountPalindrome(text, i, i, result);
            
            // try each pair of characters as a middle of a palindrome
            CountPalindrome(text, i, i + 1, result);
        }

        return result[0];
    }

    private static void CountPalindrome(string text, int lo, int hi, string[] result)
    {
        while (lo >= 0 && hi < text.Length && text[lo] == text[hi])
        {
            int length = hi - lo + 1;
            if (length > result[0].Length)
            {
                // update the longest palindromic substring
                result[0] = text.Substring(lo, length);
            }

            lo--;
            hi++;
        }
    }

The time complexity is O(n^2).