Longest Palindromic Substring

Given a string s, return the longest substring of s that is a palindrome, meaning it reads the same forwards and backwards. If several have the same maximum length, any of them is accepted. This is LeetCode 5. The limits are 1 <= s.length <= 1000, and s holds only digits and English letters.

The page gives two solutions, both O(n^2) time. Solution 1 grows a palindrome outward from each possible center and uses O(1) extra space. Solution 2 fills a dynamic programming table that records which substrings are palindromes.

Example 1
Input: s = "babad"
Output: "bab"
Explanation: "aba" has the same length and is also accepted.
Example 2
Input: s = "cbbd"
Output: "bb"
Example 3
Input: s = "ac"
Output: "a"
Explanation: no two characters match, so any single character is a palindrome of length 1.

How to Think About It

Step 1: The direct approach

There are about n^2 / 2 substrings, and checking whether one is a palindrome takes up to n comparisons. Checking all of them is O(n^3), close to 10^8 character comparisons when n = 1000. It works but wastes a lot of effort.

Step 2: Palindromes are nested

Strip the first and last characters from a palindrome and what remains is still a palindrome. Turn that around: s[i..j] is a palindrome exactly when s[i] == s[j] and the inside s[i+1..j-1] is a palindrome. Each answer reuses a smaller one, so no substring needs to be checked from scratch.

Step 3: Grow from the middle

Every palindrome has a middle. For odd lengths like "aba" it is one character; for even lengths like "abba" it is the gap between two equal characters. A string of length n has n character centers and n - 1 gap centers.

From a center, step outward while the two ends match. By Step 2, every stretch you pass through is a palindrome, and the first mismatch ends the search, because any longer string around this center would contain that mismatch. This is Solution 1.

Step 4: Or store the answers in a table

Step 2 is also a dynamic programming recurrence. Let isPal[i][j] say whether s[i..j] is a palindrome. Filling the table from short substrings to long ones guarantees the inside entry is ready when it is needed. This is Solution 2. The same table, used for counting instead of finding the longest, solves Palindromic Substrings.

Walkthrough

Solution 1 on Example 1, s = "babad". For each index the table shows the longest palindrome around the character itself (odd) and around the gap to its right (even).

centerCharacterOdd lengthEven lengthBest after this center
0b10"b"
1a3 ("bab")0"bab"
2b3 ("aba")0"bab", the tie does not replace it
3a10"bab"
4d10"bab"

For Example 2, "cbbd", the only length above 1 is the even length 2 at center 1, between the two b characters, so the answer is "bb".

Solution 1: Expand Around Center

This method tries all 2n - 1 centers, expands each one while the characters on both sides match, and keeps the longest result.

  • Two calls per index: expand(s, center, center) handles odd lengths and expand(s, center, center + 1) handles even lengths. The even call returns 0 when the two characters differ.
  • The length formula: the loop stops one step past the palindrome on each side, so its length is right - left - 1, not right - left + 1.
  • Turning a length back into bounds: start = center - (len - 1) / 2 and end = center + len / 2 work for both parities. For "bb" at center 1, that gives start 1 and end 2.
  • Ties: the test len > end - start + 1 is strict, so the first longest palindrome found is kept, and "babad" returns "bab".

A common mistake is to expand only around characters, forgetting the gaps between them. Every even-length palindrome is then missed: "cbbd" returns "c" instead of "bb", and "aaaa" returns "aaa".

Java
public class LongestPalindromicSubstring {

    public String longestPalindrome(String s) {
        int start = 0;
        int end = 0;                                      // best palindrome so far is s[start..end]
        for (int center = 0; center < s.length(); center++) {
            int odd = expand(s, center, center);          // middle is one character
            int even = expand(s, center, center + 1);     // middle is the gap after it
            int len = Math.max(odd, even);
            if (len > end - start + 1) {
                start = center - (len - 1) / 2;
                end = center + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private 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;       // both ends stopped one step past the palindrome
    }

    public static void main(String[] args) {
        LongestPalindromicSubstring solver = new LongestPalindromicSubstring();
        System.out.println(solver.longestPalindrome("babad"));   // bab
        System.out.println(solver.longestPalindrome("cbbd"));    // bb
        System.out.println(solver.longestPalindrome("ac"));      // a
    }
}

Solution 2: Dynamic Programming

This method fills a boolean table where isPal[i][j] is true when s[i..j] is a palindrome, going through the substrings in order of length.

  • Short substrings: for lengths 1 and 2 the inside is empty, so matching end characters are enough. The condition len <= 2 covers both and also keeps i + 1 from passing j - 1.
  • Longer substrings: isPal[i + 1][j - 1] describes a substring two characters shorter, which an earlier pass of the outer loop has already filled.
  • Recording the answer: within one length, i runs from left to right, and only a strictly longer palindrome replaces the best. So "babad" also returns "bab", matching Solution 1.
  • Memory: at the limit n = 1000 the table holds 10^6 booleans, about 1 MB, which is fine here but grows quickly with n.

A common mistake is to fill the table with plain nested loops, i and j both going up. Then isPal[i + 1][j - 1] is read before it is set, still false, and "babad" returns "b" instead of "bab".

Java
public class LongestPalindromicSubstringDP {

    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];   // isPal[i][j]: is s[i..j] a palindrome
        int bestStart = 0;
        int bestLen = 1;
        for (int len = 1; len <= n; len++) {     // shorter substrings first
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                isPal[i][j] = s.charAt(i) == s.charAt(j) && (len <= 2 || isPal[i + 1][j - 1]);
                if (isPal[i][j] && len > bestLen) {
                    bestStart = i;
                    bestLen = len;
                }
            }
        }
        return s.substring(bestStart, bestStart + bestLen);
    }

    public static void main(String[] args) {
        LongestPalindromicSubstringDP solver = new LongestPalindromicSubstringDP();
        System.out.println(solver.longestPalindrome("babad"));   // bab
        System.out.println(solver.longestPalindrome("cbbd"));    // bb
        System.out.println(solver.longestPalindrome("ac"));      // a
    }
}

Complexity

  • Solution 1 time: O(n^2). There are 2n - 1 centers, and each expansion can run up to n / 2 steps, as in a string of one repeated letter. Most real strings stop expanding much sooner.
  • Solution 1 space: O(1) besides the returned string. Only the indices start, end, left and right are kept, whatever the length of the input.
  • Solution 2 time: O(n^2). The two loops visit each pair with i <= j exactly once, about n^2 / 2 cells, and each cell needs one comparison and one table lookup.
  • Solution 2 space: O(n^2). The isPal table has n × n entries, even though only the upper half with i <= j is used.

Which One to Use

Prefer expand around center. It has the same O(n^2) worst case, uses no table, and on most strings stops expanding early, so it is usually several times faster. The DP version is worth knowing because the same isPal table answers many other questions, such as counting palindromes or cutting a string into palindromes. Both return exactly the same substring, since both keep the leftmost of the longest palindromes. If you need O(n) time, Manacher's Algorithm reuses mirror information between centers to avoid repeated expansion.