# Longest Palindromic Substring Problem

## Description

LeetCode Problem 5.

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

Example 1:

``````1
2
3
Output: "bab"
Note: "aba" is also a valid answer.
``````

Example 2:

``````1
2
Input: s = "cbbd"
Output: "bb"
``````

Example 3:

``````1
2
Input: s = "a"
Output: "a"
``````

Example 4:

``````1
2
Input: s = "ac"
Output: "a"
``````

Constraints:

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

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));

int max_len = 0, idx_i = 0, idx_j = 0;
for (int k = 0; k < n; k ++) {
for (int i = 0; i < n-k; i ++) {
int j = i+k;
if (k == 0) {
dp[i][j] = 1;
} else if (k == 1) {
dp[i][j] = (s[i] == s[j]);
} else {
if (dp[i+1][j-1] == 1 && s[i] == s[j])
dp[i][j] = 1;
else
dp[i][j] = 0;
}

if (dp[i][j] == 1) {
if (j-i+1 > max_len) {
max_len = j - i + 1;
idx_i = i;
idx_j = j;
}
}
}
}

return s.substr(idx_i, max_len);
}
};
``````