1. 算法学习笔记(83): Manacher算法
Manacher算法，俗称马拉车，是一种专门处理回文子串问题的算法。回文串有奇偶两种形式：奇回文串和偶回文串。奇回文串相较于偶回文串更易处理，因其存在唯一的中心点。通过在原字符串两端添加一个不在字符集内的特殊字符，如空格或特定符号，可以将奇回文串转变成以普通字符为中心的奇回文串，而偶回文串则会变为以特殊字符为中心的奇回文串。
对于字符串S，定义一个数组P，表示以字符为中心的奇回文串的数量。在预处理后，P中的值对应原字符串中以特殊字符为中心的回文串。最长的回文子串长度是P中的最大值。
Manacher算法通过遍历字符串并维护中心点与边界点的位置，高效求解P数组。与Z算法类似，算法流程中，数组P值递增，内层循环执行次数不超过字符串长度，因此算法复杂度为线性。
2. 回文序列问题
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
时间复杂度： O(n^2) 两个for循环
空间复杂度： O(n^2) dp数组的大小
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
思路：动态规划得到每个子串是否为回文子串，然后从头开始回溯算法
时间复杂度：O(N * 2^N)
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
思路：
时间复杂度=空间复杂度=O(n^2)
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
通过从 S 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
示例 1：
输入：
S = 'bccb'
输出：6
解释：
6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。