What is the time complexity of Valid Palindrome II?

The time complexity is O(n) because the two-pointer technique scans the string once.

How does the two-pointer approach work for this problem?

The two-pointer approach compares characters from both ends and moves inward, allowing for one character deletion if a mismatch occurs.

What is the maximum length of string `s` in Valid Palindrome II?

The maximum length of `s` is 10^5, which requires an efficient O(n) solution.

Can Valid Palindrome II handle strings that are already palindromes?

Yes, if the string is already a palindrome, the solution will return true without any deletions.

What is the space complexity of Valid Palindrome II?

The space complexity is O(1), as the solution uses only constant extra space beyond the input string.

#680

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

验证回文串 II

给你一个字符串 s ，最多可以从中删除一个字符。请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。示例 1：输入： s = "aba" 输出： true 示例 2：输入： s = "abca" 输出： true 解释：你可以删除字符 'c' 。示…

双指针字符串贪心

题目描述

给你一个字符串 s，最多可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

输入：s = "aba"
输出：true

示例 2：

输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。

示例 3：

输入：s = "abc"
输出：false

提示：

1 <= s.length <= 10⁵
s 由小写英文字母组成

lightbulb

解题思路

方法一：双指针

我们用两个指针分别指向字符串的左右两端，每次判断两个指针指向的字符是否相同，如果不相同，则判断删除左指针对应的字符后字符串是否是回文字符串，或者判断删除右指针对应的字符后字符串是否是回文字符串。如果两个指针指向的字符相同，则将左右指针都往中间移动一位，直到两个指针相遇为止。

如果遍历结束，都没有遇到指针指向的字符不相同的情况，那么字符串本身就是一个回文字符串，返回 true 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def check(i, j):
            while i < j:
                if s[i] != s[j]:
                    return False
                i, j = i + 1, j - 1
            return True

        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return check(i, j - 1) or check(i + 1, j)
            i, j = i + 1, j - 1
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should demonstrate a clear understanding of two-pointer techniques.
question_mark
Look for how well the candidate handles the one-character deletion requirement.
question_mark
Evaluate the ability to optimize and keep the solution space-efficient.

warning

常见陷阱

外企场景

error
Not handling the case when characters match early but fail when removing one.
error
Over-complicating the solution by using extra data structures like arrays or sets.
error
Missing edge cases like strings that are already palindromes or too short to modify.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if the string can be a palindrome with two or more deletions.
arrow_right_alt
Use this technique with longer strings for performance optimization.
arrow_right_alt
Consider case sensitivity when expanding the problem scope.

help

常见问题

外企场景

继续练习

#763 划分字母区间 #942 增减字符串匹配 #1147 段式回文