Link to Question

MEDIUM

Longest Palindromic Substring

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

Example

Input:

s = "babad"

Output:

"bab"

Explanation:
"aba" is also a valid answer.

---

Constraints

• 1 ≤ s.length ≤ 1000
• s consist of only digits and English letters.

---

Solution: Dynamic Programming

• Time Complexity: O(n²), where n is the length of the string. The dynamic programming table is filled for all substrings.
• Space Complexity: O(n²), due to the DP table storing palindrome status for all substring pairs.

C++

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        string ans = "";

        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                if (s[i] == s[j])
                    if (j - i <= 1)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i+1][j-1];

                if (dp[i][j] && j - i + 1 > ans.size())
                    ans = s.substr(i, j - i + 1);
            }
        }
        return ans;
    }
};