060 · Valid Palindrome II

Problem

给定一个字符串 s。

请判断它是否可以成为回文字符串。

这里允许你最多删除一个字符。

也就是说：

• 如果 s 本身已经是回文字符串，返回 true
• 如果删除其中一个字符以后可以变成回文字符串，返回 true
• 如果无论删除哪个字符都不能变成回文字符串，返回 false

回文字符串指的是从左往右读和从右往左读完全一样的字符串。

例如：

s = "aba"

它本身就是回文字符串，所以返回：

true

再例如：

s = "abca"

如果删除字符 "c"，剩下的是：

"aba"

这是一个回文字符串，所以也返回：

true

注意：最多只能删除一个字符。不能为了得到回文字符串而删除两个或更多字符。

Examples

示例 1

Input:  s = "aba"
Output: true

解释："aba" 本身就是回文字符串，不需要删除任何字符。

示例 2

Input:  s = "abca"
Output: true

解释：删除 "c" 以后得到 "aba"，它是回文字符串。

示例 3

Input:  s = "abc"
Output: false

解释：最多只能删除一个字符。无论删除 "a"、"b" 还是 "c"，剩下的字符串都不是回文字符串。

Constraints

• \(1 \leq\) s.length \(\leq 10^5\)
• s 只由小写英文字母组成

Link

• Original Problem

---

→ Solution