Start learning free

LESSON 453 OF 535 · DYNAMIC PROGRAMMING

Longest Palindromic Substring in C++: Expand Around Center in O(n²)

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

    The function longestPalindrome receives a string s and returns its longest palindromic substring. A palindrome reads the same forward and backward, like "racecar" or "abba". A substring is a run of consecutive characters, so "bcd" is a substring of "abcde" and "ace" is not. When several palindromes share the greatest length, the one that starts first, furthest to the left, is returned.

    For "babad" the answer is "bab": "aba" is just as long, but "bab" starts earlier. For "cbbd" it is "bb", an even-length palindrome. For "abacdfgdcaba" it is "aba", the first of its two occurrences. The string contains English letters and digits, and uppercase and lowercase letters are different characters, so "Aa" is not a palindrome.

    The lesson asks for O(n²) time and O(1) extra space besides the returned string.

    Approach: grow palindromes from their centers

    Checking every substring separately costs O(n³): about n²/2 substrings, each up to n characters long. Looking at palindromes from the middle is cheaper. 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. Start with two positions, left and right, on the same character for an odd center or on two neighbours for an even one. While both are inside the string and their characters are equal, move them one step outward. When they stop, the palindrome lies strictly between them and has right - left - 1 characters. That is the longest palindrome around the center, because a mismatch can't be fixed by going further out.

    The main loop visits every index i and expands twice: from (i, i) for the odd center and from (i, i + 1) for the even center after it. It keeps the start and length of the best palindrome so far and replaces them only when it finds a strictly longer one. The centers go from left to right, so among equally long palindromes the first one stays.

    Here is how the expansion behaves on "babad". From (1, 1) (the a) the ends move out to b and b, which match, and then run off the string, so the length is 3. From (1, 2) the characters a and b differ at once, so the length is 0. On "cbbd", (1, 2) starts on the two bs and gives 2. On "ab", (0, 1) gives 0.

    A table that records whether each s[i..j] is a palindrome also works in O(n²) time, but it needs O(n²) space. Expanding keeps only a few numbers.

    Step by step

    1. Create bestStart and bestLen, both 0: where the best palindrome so far starts and how many characters it has. The substring itself is cut out once, at the end.
    2. Loop over every index i. The bound is (int) s.size(), so both sides of the comparison are ints.
    3. Expand around (i, i) with a helper called expand and store the result in odd. The lesson uses the helper before writing it, which keeps the loop short.
    4. Expand around (i, i + 1) and store the result in even. If the two characters differ, or i is the last index, the length is 0.
    5. Take the larger of the two with max and call it length.
    6. Compare with bestLen. The test is strict (length > bestLen), so an equally long palindrome further right never replaces the first one.
    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 before its left middle s[i]. In integer arithmetic both are (length - 1) / 2.
    8. Set bestLen to length.
    9. Return s.substr(bestStart, bestLen).
    10. Write expand as a method that returns an int and takes const string& s and two ints, left and right.
    11. Loop while both ends are valid and match: left >= 0, right < (int) s.size() and s[left] == s[right].
    12. Move outward with 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.

    The solution in C++

    class Solution {
public:
    string longestPalindrome(string s) {
        int bestStart = 0;
        int bestLen = 0;
        for (int i = 0; i < (int) s.size(); i++) {
            int odd = expand(s, i, i);
            int even = expand(s, i, i + 1);
            int length = max(odd, even);
            if (length > bestLen) {
                bestStart = i - (length - 1) / 2;
                bestLen = length;
            }
        }
        return s.substr(bestStart, bestLen);
    }

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

    The C++ details worth a closer look:

    • Signed and unsigned. s.size() is unsigned, while left and right are ints that can reach -1. Comparing an int with an unsigned value converts the int to unsigned, which turns -1 into a huge number and makes comparisons quietly wrong. Casting the size to int keeps every comparison between ints.
    • Short-circuit order. The two range checks come before s[left] == s[right]. && stops at the first false operand, so the characters are read only when both indexes are valid.
    • Parameters are copies of the ints. C++ passes left and right by value, so moving them inside expand doesn't change the caller's variables. That is why the length is returned.
    • const string&. The helper reads s where it is instead of copying up to 1000 characters on each of the 2n calls.
    • Members can call each other in any order. Inside a class, longestPalindrome can call expand even though expand is written below it.
    • substr(start, count). The second argument is a number of characters, not an end index.

    Complexity

    Time: O(n²). There are 2n - 1 centers, and each expansion moves at most about n / 2 steps in each direction. The total work is bounded by a constant times n².

    Space: O(1) extra, besides the returned string. The method keeps a handful of integers. substr allocates only the result.

    Edge cases and common mistakes

    • One character. "a" returns "a": the odd expansion gives 1 and the even one gives 0.
    • No repeated characters. "ab" returns "a". Every palindrome has length 1, and the strict comparison keeps the first.
    • Case matters. "Aa" returns "A", because 'A' and 'a' are different characters.
    • Only odd centers. Skipping the (i, i + 1) call misses palindromes like "bb" and "abba".
    • Using >= instead of >. Each later palindrome of equal length would replace the first, and "babad" would give "aba".
    • Wrong start. Using i - length / 2 works for odd lengths but is off by one for even ones: for "cbbd" it would start at 0 and return "cb".
    • The whole string is a palindrome. "racecar" returns itself, and "abba" too.
    • A long palindrome inside a longer string. "forgeeksskeegfor" returns "geeksskeeg", found from the even center between the two s characters.

    Testing

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