5. Longest Palindromic Substring

Problem Statement

Given a string s, return the longest palindromic substring in s.

Examples

Example 1:

Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

Difficulty

Medium

Solution 1: Dynamic Programming

Approach:

We use a 2D array dp[i][j] to track whether the substring s[i...j] is a palindrome. The core idea is that a string is a palindrome if its first and last characters are equal and the inner substring is also a palindrome.

Specifically, dp[i][j] is true if s[i] == s[j] and either the substring length is less than or equal to 3 (like "aba" or "aa"), or the precomputed value dp[i+1][j-1] is true. We iterate through all possible lengths and starting positions, filling the table to find the longest substring where dp[i][j] holds true.

Time Complexity: O(n²)
Space Complexity: O(n²) to store the DP table.

---

Solution 2: Central Expansion (Optimal)

Approach:

A palindrome mirrors around its center. We can iterate through each possible center (of which there are 2n - 1, including characters and the gaps between them) and expand outwards. As long as the characters on the left and right match, we continue expanding. This method is more efficient than Dynamic Programming because it only requires constant space.

Java

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

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

C++

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) return s;
        int start = 0, maxLen = 1;
        auto expand = [&](int l, int r) {
            while (l >= 0 && r < n && s[l] == s[r]) {
                if (r - l + 1 > maxLen) {
                    start = l;
                    maxLen = r - l + 1;
                }
                l--; r++;
            }
        };
        for (int i = 0; i < n; ++i) {
            expand(i, i);
            expand(i, i + 1);
        }
        return s.substr(start, maxLen);
    }
};

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(l, r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l + 1 : r]

        ans = ""
        for i in range(len(s)):
            s1 = expand(i, i)
            s2 = expand(i, i + 1)
            if len(s1) > len(ans): ans = s1
            if len(s2) > len(ans): ans = s2
        return ans

Time Complexity: O(n²)
Space Complexity: O(1)

← All Problems