Interview Classic 150 Questions P5 Longest Palindromic Substring

---

Timeline

timeline

2025-12-15

init

dynamic programming

---

Problem:

P5 Longest Palindromic Substring

https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-interview-150

Let$dp[i][j]$be$s[i..j]$the length of the palindromic substring, if$s[i..j]$is not a palindromic substring, then$dp[i][j]=0$, otherwise,$dp[i][j] = j-i+1$; therefore, the substring length$len = j-i+1$whether it is a palindromic substring depends on the palindromic substring of len-1, so in the loop, iterate by increasing len.

During initialization:

• When len == 1,$dp[i][i] = 1$;
• When len == 2, $dp[i][i+1] = 2$ (if$s[i] == s[i+1]$)

#include <string>
#include <vector>

using std::string;
using std::vector;

class Solution {
    public:
        string longestPalindrome(string s)
        {
                int i, j, len, end_idx, n = s.size();
                int max_len = 1, reti = 0;
                // dp[i][j] being 0 means s[i..j] is not a palindrome, greater than 0 means j-i+1
                vector<vector<int> > dp(n, vector<int>(n, 0));

                for (i = 0; i < n; i++) { // len == 1
                        dp[i][i] = 1;
                }

                len = 2;
                for (i = 0; i + len - 1 < n; i++) { // len == 2
                        if (s[i] == s[i + len - 1]) {
                                dp[i][i + len - 1] = 2;
                                if (dp[i][i + len - 1] > max_len) {
                                        max_len = dp[i][i + len - 1];
                                        reti = i;
                                }
                        }
                }

                for (len = 3; len <= n; len++) {
                        for (i = 0; i + len - 1 < n; i++) { // s[i..i+len-1]
                                end_idx = i + len - 1;
                                if (s[i] == s[end_idx] && dp[i + 1][end_idx - 1] != 0) {
                                        dp[i][end_idx] = dp[i + 1][end_idx - 1] + 2;
                                        if (dp[i][end_idx] > max_len) {
                                                max_len = dp[i][end_idx];
                                                reti = i;
                                        }
                                }
                        }
                }

                return s.substr(reti, max_len);
        }
};

leetcode hot 100 rewrite:
Pay attention to the dependency relationship: if the former depends on the latter, then iterate from back to front; otherwise, from front to back.

#include <string>
#include <vector>

using std::string;
using std::vector;

class Solution {
    public:
        string longestPalindrome(string s)
        {
                int i, j, n = s.size();
                int max_len = 1, start = 0;
                vector<vector<int> > dp(n, vector<int>(n, 0));

                for (i = 0; i < n; i++)
                        dp[i][i] = 1;

                for (i = n - 1; i >= 0; i--) {
                        for (j = i + 1; j < n; j++) {
                                if (s[j] == s[i]) {
                                        if (j - i == 1)
                                                dp[i][j] = 2;
                                        else if (j - i > 1 && dp[i + 1][j - 1] > 0)
                                                dp[i][j] = dp[i + 1][j - 1] + 2;
                                        else
                                                dp[i][j] = 0;

                                        if (dp[i][j] > max_len) {
                                                max_len = dp[i][j];
                                                start = i;
                                        }

                                } else {
                                        dp[i][j] = 0;
                                }
                        }
                }

                return s.substr(start, max_len);
        }
};