Start learning free

LESSON 454 OF 536 · DYNAMIC PROGRAMMING

Longest Palindromic Substring in Java: Expand Around Center, 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

    JAVA · DYNAMIC PROGRAMMING

    Longest Palindromic Substring in Java, explained

    Problem overview

    The method 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" but "ace" is not. When several palindromes share the greatest length, the one that starts furthest to the left is returned.

    For "babad" the result is "bab". The substring "aba" has the same length, but "bab" starts first. For "cbbd" the result is "bb", an even-length palindrome. For "abacdfgdcaba" it is "aba", which appears at both ends, and the first one counts. The string contains English letters and digits, and case matters, so "Aa" is not a palindrome.

    The statement 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³): there are about n²/2 substrings and each check reads up to n characters. The faster view starts from the middle. 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 with n characters has 2n - 1 centers, which are n characters and n - 1 gaps.

    From a center, expand: put left and right on the two middle positions and move them outward while both stay inside the string and the characters match. When the loop stops, the palindrome between the two positions is the longest one around that center.

    The loop visits each index i and tries two centers: the character s[i] (start with left = right = i) and the gap after it (start with left = i, right = i + 1). For "babad" the expansions give these lengths:

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

    At i = 1 the odd expansion finds "bab" (length 3). At i = 2 it finds "aba", also length 3, but the best is replaced only by a strictly longer palindrome, so "bab" stays. Centers are visited from left to right, so this rule keeps the first of the longest ones.

    Other methods exist. A table dp[i][j] that says whether s[i..j] is a palindrome has the same time but needs O(n²) space, and Manacher's algorithm reaches O(n) time. This lesson uses center expansion because it is short and meets the space limit.

    Step by step

    1. Create bestStart and bestLen, both 0. Remembering the start and the length is enough, and the substring is cut out once at the end.
    2. Loop i over every index of s. Each index supplies two centers: a character and the gap after it.
    3. Call expand(s, i, i) and store the result in odd. The helper is written last. Assuming it exists keeps this loop short.
    4. Call expand(s, i, i + 1) and store the result in even. When the two characters differ, or i is the last index, the length is 0.
    5. Take the larger of the two with Math.max, as length.
    6. Compare with length > bestLen. It is strict, so a palindrome that is just as long but starts later never replaces the earlier one.
    7. Compute the start as i - (length - 1) / 2. An odd palindrome has (length - 1) / 2 characters before its middle. An even one has length / 2 - 1 characters before its left middle, and with integer division both come to (length - 1) / 2.
    8. Update bestLen to length.
    9. Return s.substring(bestStart, bestStart + bestLen).
    10. Write expand as a method of the same class that returns an int and takes the string and the two ends.
    11. Loop while the ends are valid and equal: left >= 0, right < s.length() and the two characters match.
    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.

    The solution in Java

    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, bestStart + bestLen);
    }

    int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

    The Java details worth a closer look:

    • Short-circuit &&. The two bounds checks come before s.charAt. When one fails, Java skips the rest, so charAt is never called with an index outside the string, which would throw a StringIndexOutOfBoundsException.
    • charAt and ==. s.charAt(i) returns a char, a primitive, so == compares the characters themselves. That differs from strings, which need equals. Characters are compared by code, which is why 'A' and 'a' differ.
    • Arguments are passed by value. Changing left and right inside expand doesn't affect the caller's variables. The caller only receives the returned length.
    • Integer division. (length - 1) / 2 drops the remainder. Since length is at least 1 whenever the if runs, the numerator is never negative, so this rounds down.
    • substring(start, end) leaves out the end index, so bestStart + bestLen as the end gives exactly bestLen characters.
    • Method without a modifier. expand has default (package-private) access, which is fine for a helper called from the same class.

    Complexity

    There are 2n - 1 centers, and each expansion takes at most about n / 2 steps, so the time is O(n²). The method keeps only a few integers, so the extra space is O(1), not counting the returned string.

    Edge cases and common mistakes

    • Forgetting even-length palindromes. Calling only expand(s, i, i) misses "bb" in "cbbd" and would return "b".
    • Using >= in the comparison. A later palindrome of the same length would replace the earlier one. For "babad" the result would be "aba" instead of "bab".
    • Checking the characters before the bounds. Reversing the order of the conditions in the while loop throws an exception at the ends of the string.
    • Wrong length formula. The loop stops one step beyond the palindrome on both sides, which is why the length is right - left - 1 and not right - left.
    • No palindrome longer than one character. Any single character is a palindrome, so "abcd" returns "a", the first one.
    • Case. "Aa" returns "A", because uppercase and lowercase letters differ.

    Testing

    These results come from running the solution:

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