# 5. Longest Palindromic Substring | LeetCode Solution

## 5. Longest Palindromic Substring | LeetCode Solution

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.
class Solution {
public:

string longestPalindrome(string s) {
string ans="";
vector<vector<bool>>dp(s.length(),vector<bool>(s.length(),false));
for(int g=0; g<s.length(); g++){
for(int i=0,j=g; j<s.length(); j++,i++){
if(g==0)dp[i][j]=true;
else if(g==1 && s[i]==s[j])dp[i][j]=true;
else{
if(s[i]==s[j] && dp[i+1][j-1])dp[i][j]=true;
}
if(dp[i][j])ans=s.substr(i,j-i+1);
}
}
return ans;
}
};

Optimised Solution

class Solution {
public:
int expand(string s,int start,int end){
while(start>=0 && end<s.length() && s[start]==s[end]){
start--;
end++;
}
return end-start-1;
}

string longestPalindrome(string s) {
int n=s.length();
int start=0,end=0;
for(int i=0; i<n; i++){
int odd=expand(s,i,i);
int even=expand(s,i,i+1);
int len=max(odd,even);
if(len>end-start){
start=i-(len-1)/2;
end=i+len/2;
}
}
cout<<end<<" "<<start;
return s.substr(start,end-start+1);
}
};