Problem Statement:

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

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Solution:

We build a boolean 2-D table dp of size n by n such that dp[i][j]stores whether or not the substring starting at i and ending at j is a palindrome.

We start with len=1 and go upto len=n. Note that if the substring starts at index i and has length len then the substring will end at j=i+len-1.

Generally we can say that s(i,...,j) is a palindrome if the substring s(i+1,...,j-1) is a palindrome and s[i]==s[j]. We will have to handle cases of len=1,2 separately.

Java solution:

 
class Solution 
{
    public String longestPalindrome(String s) 
    {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)dp[i][j]=false;
        String res="";
        for (int len=1; len<=n; len++)
        {
            for (int i=0; i<=n-len; i++)
            {
                int j = i+len-1;
                dp[i][j] = s.charAt(i)==s.charAt(j) && ((len<=2) || dp[i+1][j-1]);
                if (dp[i][j]) res = s.substring(i,j+1);
            }
        }
        return res;        
    }
}

C++ solution:

 
class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        int n = s.length();
        vector<vector<bool>>dp(n, vector<bool>(n,false));
        string res;
        for (int len=1; len<=n; len++)
        {
            for (int i=0; i<=n-len; i++)
            {
                int j = i+len-1;
                dp[i][j] = s[i]==s[j] && ((len<=2) || dp[i+1][j-1]);
                if (dp[i][j]) res = s.substr(i,len);
            }
        }
        return res;
    }
};