Start learning free

LESSON 457 OF 539 · DYNAMIC PROGRAMMING

Longest Palindromic Substring in C#: Expand Around the Center

Practice O(n2) Read the full explanation

You are given a string s. Return its longest palindromic substring. If several substrings have that greatest length, return the one that starts first, furthest to the left.

A palindrome reads the same forward and backward, like "racecar" or "abba". A substring is a run of consecutive characters of s: "bcd" is a substring of "abcde", but "ace" is not.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is a palindrome of length 3 too, but "bab" starts first.
No substring of length 4 or 5 is a palindrome.

Example 2:

Input: s = "cbbd"
Output: "bb"
Explanation: A palindrome of even length, like "bb", has its middle between two characters.

Example 3:

Input: s = "abacdfgdcaba"
Output: "aba"
Explanation: "aba" appears at the start and at the end, and the first one is returned.
"abacd" read backward is "dcaba", which also appears in s, but neither of them is a palindrome.

 

Constraints:

  • 1 <= s.length <= 1000
  • s is made of English letters and digits only. Uppercase and lowercase letters are different characters: "Aa" is not a palindrome.

Note:

Your algorithm should run in O(n2) time and use O(1) extra space besides the returned string, where n is the length of s.



Checking every substring on its own takes O(n3): about n2/2 substrings, each up to n characters long. Look at palindromes from the middle instead. Every palindrome has a center: its middle character when its length is odd, or the gap between its two middle characters when the length is even. A string of n characters has 2n - 1 centers: n characters and n - 1 gaps.

From a center, expand: start with two positions left and right (the same character, or two neighbours), and move them one step outward while both are inside s and their characters are equal. When they stop, the palindrome between them has right - left - 1 characters, and it is the longest one around that center. A helper that does this and returns the length, called for the centers (i, i) and (i, i + 1) of every i, finds the longest palindrome at each center.
A palindrome of length length centered at i starts at i - (length - 1) / 2, rounded down. Keep the best start and length, and replace them only by a strictly longer palindrome: the centers go from left to right, so the first of the longest ones stays.

There are 2n - 1 centers, and each expansion takes at most n / 2 steps: O(n2) time. Only a few numbers are kept: O(1) extra space, besides the returned string.
A table dp[i][j] telling whether s[i..j] is a palindrome works too, in the same time but with O(n2) space. Manacher's algorithm even finds the answer in O(n), but it goes beyond this lesson.
STEP 1 OF 13
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    Longest Palindromic Substring in C#, explained

    Problem overview

    LongestPalindrome receives a string s and returns its longest palindromic substring. A palindrome reads the same forward and backward. A substring is a run of consecutive characters. When several palindromes share the greatest length, the one that starts first wins. Uppercase and lowercase letters are different characters, so "Aa" is not a palindrome.

    For "babad" the answer is "bab": "aba" is just as long, but "bab" starts first. For "cbbd" it is "bb", an even-length palindrome.

    Approach: grow palindromes from their centers

    Checking every substring takes O(n^3): about n^2 / 2 substrings, each up to n characters long to check. Look at palindromes from the middle instead. Every palindrome has a center: its middle character when the length is odd, or the gap between its two middle characters when the length is even. A string of n characters has 2n - 1 centers, n characters and n - 1 gaps.

    From a center, expand: put two positions left and right on it, and move them outward one step at a time while both are inside the string and their characters are equal. When they stop, the palindrome between them has right - left - 1 characters, and it is the longest one around that center.

    For "babad" the helper gives these lengths for the odd center at i and the even center just after i:

    0 odd=1 even=0
1 odd=3 even=0
2 odd=3 even=0
3 odd=1 even=0
4 odd=1 even=0

    The first length of 3, at i = 1, is "bab". The same length at i = 2 is "aba", but it is not strictly longer, so "bab" stays.

    Step by step

    1. Create bestStart and bestLen, both 0. The start and the length are all you need to remember. The substring is cut out once, at the end.
    2. Loop i over every index. Each i gives two centers: the character s[i] and the gap after it.
    3. Call Expand(s, i, i) into odd. Both ends start on s[i], which finds the longest odd-length palindrome with that middle. You can write this call before Expand exists and write the helper last.
    4. Call Expand(s, i, i + 1) into even. The ends start on two neighbours. If they differ, or i is the last index, the length is 0.
    5. Take Math.Max(odd, even) as length, the longest palindrome around position i.
    6. Compare with length > bestLen, strictly. The centers go from left to right, so a palindrome as long as the best one starts further right and must not replace it.
    7. Set bestStart to i - (length - 1) / 2. An odd palindrome has (length - 1) / 2 characters before its middle s[i]. An even one has length / 2 - 1 characters before s[i], its left middle. Integer division rounds both down to (length - 1) / 2.
    8. Set bestLen to length.
    9. Return s.Substring(bestStart, bestLen) after the loop.
    10. Write Expand. It takes the string and two ends, and returns an int.
    11. Loop while left >= 0, right < s.Length and s[left] == s[right]. The range checks come first, and && stops at the first false one, so the characters are read only when both ends are inside the string.
    12. Move outward: left-- and right++.
    13. Return right - left - 1. The loop stops one step past the palindrome on each side, so the palindrome runs from left + 1 to right - 1. When the starting characters differ, that is 0.

    The solution in C#

    class Solution {
    public string LongestPalindrome(string s) {
        int bestStart = 0;
        int bestLen = 0;
        for (int i = 0; i < s.Length; i++) {
            int odd = Expand(s, i, i);
            int even = Expand(s, i, i + 1);
            int length = Math.Max(odd, even);
            if (length > bestLen) {
                bestStart = i - (length - 1) / 2;
                bestLen = length;
            }
        }
        return s.Substring(bestStart, bestLen);
    }

    int Expand(string s, int left, int right) {
        while (left >= 0 && right < s.Length && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

    The C# details worth knowing:

    • s.Substring(start, length) takes a start index and a number of characters, not an end index.
    • left and right are ints, passed by value. Moving them inside Expand does not change anything in LongestPalindrome, which is why the helper returns a length.
    • s[left] is a char, and == on two chars compares their values. 'A' and 'a' are different values.
    • A method without an access modifier, like Expand, is private in a class. The same class can call it by its name alone.

    Complexity

    Time: O(n^2). There are 2n - 1 centers and each expansion takes at most about n / 2 steps. A string like "aaaa" reaches that worst case.

    Space: O(1) besides the returned string: a few integers.

    An even palindrome is why the helper is called twice per index. In "cbbd", Expand(s, 1, 2) starts on the two bs, which match, then moves to c and d, which do not. The loop stops with left = 0 and right = 3, so the length is 3 - 0 - 1 = 2. For "abc", Expand(s, 2, 3) stops at once, because right is already past the end, and returns 3 - 2 - 1 = 0.

    Edge cases and common mistakes

    • One character. "a" returns "a". The odd expansion gives 1.
    • No repeated letters. "abc" returns "a", the first character, because every palindrome has length 1 and only a strictly longer one replaces the best.
    • Case matters. "Aa" returns "A".
    • Whole string. "racecar" returns "racecar", and "aaaa" returns "aaaa".
    • Forgetting even centers. Using only Expand(s, i, i) misses "bb" in "cbbd" and returns "c".
    • Using >= instead of >. Ties would go to the later palindrome: "babad" would return "aba".
    • Off-by-one in the start. The start comes from the center and the length, not from left and right after the loop, which have moved one step too far.

    Testing

    • "babad" gives bab.
    • "cbbd" gives bb.
    • "abacdfgdcaba" gives aba.
    • "a" gives a.
    • "Aa" gives A.
    • "abc" gives a.
    • "aaaa" gives aaaa.
    • "racecar" gives racecar.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free