Medium
题目描述
给你一个由小写英文字母组成的字符串 s。
如果一个子串在删除恰好一个字符后能变成回文串，那么这个子串就是几乎回文的。
返回 s 中最长几乎回文子串的长度。
示例 1：
输入：s = "abca"
输出：4
解释：
选择子串 "abca"。
- 删除 "abca" 中的 'c'。
- 字符串变成 "aba"，这是一个回文串。
- 因此，"abca" 是几乎回文的。
示例 2：
输入：s = "abba"
输出：4
解释：
选择子串 "abba"。
- 删除 "abba" 中的任意一个字符。
- 字符串变成 "bba" 或 "abb"，都可以重排成回文串。
- 因此，"abba" 是几乎回文的。
示例 3：
输入：s = "zzabba"
输出：5
解释：
选择子串 "zabba"。
- 删除 "zabba" 中的 'z'。
- 字符串变成 "abba"，这是一个回文串。
- 因此，"zabba" 是几乎回文的。
约束条件：
- 2 <= s.length <= 2500
- s 只包含小写英文字母。
解题思路
这道题要求找到最长的几乎回文子串。几乎回文是指删除恰好一个字符后能变成回文的字符串。
核心思路：
中心扩展法：对于每个可能的中心点（奇数长度和偶数长度），向两边扩展寻找几乎回文串。
贪心策略：从中心开始扩展，当遇到第一个不匹配的字符对时，有两种选择：
- 删除左侧字符，继续检查剩余部分是否为回文
- 删除右侧字符，继续检查剩余部分是否为回文
- 取两种选择中较长的结果
实现细节：
- 对于每个中心，首先扩展所有匹配的字符对
- 遇到第一个不匹配时，分别尝试跳过左侧和右侧字符
- 检查跳过一个字符后剩余部分是否为严格回文
- 维护全局最大长度
这种方法的优势是能够高效地处理所有可能的中心位置，并在遇到不匹配时智能地选择最优的删除策略。
代码实现
class Solution {
public:
int almostPalindromic(string s) {
int n = s.length();
int maxLen = 0;
auto isPalindrome = [&](int left, int right) -> bool {
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
};
auto expandAroundCenter = [&](int left, int right) -> int {
// 先扩展所有匹配的字符
while (left >= 0 && right < n && s[left] == s[right]) {
left--;
right++;
}
// 如果已经到边界，说明是完整回文，长度为right-left-1
if (left < 0 || right >= n) {
return right - left - 1;
}
// 遇到不匹配，尝试删除左侧或右侧字符
int option1 = 0, option2 = 0;
// 选项1：删除左侧字符
if (isPalindrome(left + 1, right)) {
option1 = right - left;
}
// 选项2：删除右侧字符
if (isPalindrome(left, right - 1)) {
option2 = right - left;
}
return max(option1, option2);
};
// 尝试所有可能的中心
for (int i = 0; i < n; i++) {
// 奇数长度中心
maxLen = max(maxLen, expandAroundCenter(i, i));
// 偶数长度中心
if (i < n - 1) {
maxLen = max(maxLen, expandAroundCenter(i, i + 1));
}
}
return maxLen;
}
};
class Solution:
def almostPalindromic(self, s: str) -> int:
n = len(s)
max_len = 0
def is_palindrome(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def expand_around_center(left, right):
# 先扩展所有匹配的字符
while left >= 0 and right < n and s[left] == s[right]:
left -= 1
right += 1
# 如果已经到边界，说明是完整回文
if left < 0 or right >= n:
return right - left - 1
# 遇到不匹配，尝试删除左侧或右侧字符
option1 = option2 = 0
# 选项1：删除左侧字符
if is_palindrome(left + 1, right):
option1 = right - left
# 选项2：删除右侧字符
if is_palindrome(left, right - 1):
option2 = right - left
return max(option1, option2)
# 尝试所有可能的中心
for i in range(n):
# 奇数长度中心
max_len = max(max_len, expand_around_center(i, i))
# 偶数长度中心
if i < n - 1:
max_len = max(max_len, expand_around_center(i, i + 1))
return max_len
public class Solution {
public int AlmostPalindromic(string s) {
int n = s.Length;
int maxLen = 0;
bool IsPalindrome(int left, int right) {
while (left < right) {
if (s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
int ExpandAroundCenter(int left, int right) {
// 先扩展所有匹配的字符
while (left >= 0 && right < n && s[left] == s[right]) {
left--;
right++;
}
// 如果已经到边界，说明是完整回文
if (left < 0 || right >= n) {
return right - left - 1;
}
// 遇到不匹配，尝试删除左侧或右侧字符
int option1 = 0, option2 = 0;
// 选项1：删除左侧字符
if (IsPalindrome(left + 1, right)) {
option1 = right - left;
}
// 选项2：删除右侧字符
if (IsPalindrome(left, right - 1)) {
option2 = right - left;
}
return Math.Max(option1, option2);
}
// 尝试所有可能的中心
for (int i = 0; i < n; i++) {
// 奇数长度中心
maxLen = Math.Max(maxLen, ExpandAroundCenter(i, i));
// 偶数长度中心
if (i < n - 1) {
maxLen = Math.Max(maxLen, ExpandAroundCenter(i, i + 1));
}
}
return maxLen;
}
}
var almostPalindromic = function(s) {
const n = s.length;
let maxLen = 0;
const isPalindrome = (left, right) => {
while (left < right) {
if (s[left] !== s[right]) return false;
left++;
right--;
}
return true;
};
const expandAroundCenter = (left, right) => {
// 先扩展所有匹配的字符
while (left >= 0 && right < n && s[left]
复杂度分析
| 复杂度类型 | 复杂度值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 对每个中心进行扩展，最坏情况下每次扩展需要O(n)时间 |
| 空间复杂度 | O(1) | 只使用常数额外空间 |