Longest Palindromic Substring Problem
Description
LeetCode Problem 5.
Given a string s, return the longest palindromic substring in s.
Example 1:
1
2
3
Input: s = "babad"
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);
}
};