Problem Statement

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

Example 1:

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

Example 2:

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

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters (lower-case and/or upper-case),

Problem Link

Longest Palindromic Substring - LeetCode

Code

class Solution {
public:
    string longestPalindrome(string s) {
        
        int n = s.size();
        
        bool isP[n][n];
        
        for(int gap=0;gap<n;gap++)
        {
            for(int i=0,j=gap;j<n;i++,j++)
            {
                if(!gap)
                    isP[i][j] = true;
                
                else if(gap==1)
                {
                    if(s[i]==s[j])
                        isP[i][j] = true;
                    else
                        isP[i][j] = false;
                }
                
                else
                {
                    if(s[i]==s[j])
                        isP[i][j] = isP[i+1][j-1];
                    else
                        isP[i][j] = false;
                }
            }
        }
        
        bool dp[n][n];
        int maxlen = 1;
        int start = 0;
         for(int gap=0;gap<n;gap++)
         {
            for(int i=0,j=gap;j<n;i++,j++)
            {
                if(isP[i][j] and j-i+1>maxlen)
                {
                    maxlen = j-i+1;
                    start = i;
                }
            }
          }
        return s.substr(start,maxlen);
    
        
        
    }
};