https://leetcode.cn/problems/longest-palindromic-substring

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路：利用动态规划，如果 s[i] == s[j]，并且中间的子串 s[i+1..j-1] 也是回文，那么 s[i..j] 也是回文, 详细逻辑见实现

C#实现

public class Solution {
    public string LongestPalindrome(string s) {
        if (string.IsNullOrEmpty(s)) {
            return s;
        }
        // n：字符串长度。
        // dp[i][j]：表示 s[i..j] 这个子串是否为回文。
        // true 表示回文。
        // false 表示不是回文。
        // left, right：记录当前找到的最长回文子串的起始和结束下标。
        int n = s.Length;
        bool[,] dp = new bool[n, n];
        int left = 0;
        int right = 0;
        // 1️⃣ 为什么外层循环从 n - 2 开始，倒序？
        // 因为我们要用到 dp[i+1][j-1]，即比当前下标大的部分。
        // 倒序是为了保证计算 dp[i][j] 时，dp[i+1][j-1] 已经算好。
        for (int i = n - 2; i >= 0; i--) {
            // 2️⃣ dp[i][i] = true
            // 任何一个单独的字符，比如 "a"，本身就是回文。
            dp[i, i] = true;
            for (int j = i + 1; j < n; j++) {
                // 首尾字符相等 (s[i] == s[j])，并且：
                // 要么子串长度小于3（即是两个字符或三个字符，如 "aa" 或 "aba"，它们天然是回文）；
                // 要么中间那段 s[i+1..j-1] 也是回文。
                dp[i, j] = (s[i] == s[j]) && (j - i < 3 || dp[i + 1, j - 1]); // 小于3是因为aba一定是回文
                // 如果当前的 s[i..j] 是回文，并且长度比当前记录的更长，就更新 left 和 right。
                if (dp[i, j] && right - left < j - i) {
                    left = i;
                    right = j;
                }
            }
        }
        // 取出 left 到 right 之间的子串，即最长回文。
        return s.Substring(left, right - left + 1);
    }
}