💬 Discord
Sign In
NeetCode #178LC-680EasyTwo PointersNC 250
← Back to All Problems

#178 · #680 · Valid Palindrome II(验证回文串 II)

📌 Problem Statement & Constraints

Given a string s, return true if it can become a palindrome by deleting at most one character. Constraints: 1 <= s.length <= 10^5, lowercase letters.

💡 Core Algorithmic Approaches

  1. Walk two pointers inward while the characters match.
  2. At the first mismatch, the answer is determined by trying two options: skip the left character or skip the right character.
  3. Check whether either resulting substring is a palindrome.
  4. Because at most one deletion is allowed, this is a constant number of checks -- O(n) overall.

💻 Benchmark Python3 Implementation

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_pal(lo: int, hi: int) -> bool:
            while lo < hi:
                if s[lo] != s[hi]:
                    return False
                lo += 1
                hi -= 1
            return True

        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                # try deleting either side, once
                return is_pal(i + 1, j) or is_pal(i, j - 1)
            i += 1
            j -= 1
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): the main scan is O(n) and the two fallback checks are O(n) each, so O(n) overall.
💾 Space Complexity
O(1): index arithmetic only.

⚠️ Interview Pitfalls & Follow-ups

  • Trying to delete every character and rechecking: O(n^2).
  • Trying only one of the two deletions: the correct answer may require deleting the right character, so both must be tried.
  • Allowing more than one deletion: the fallback checks must be plain palindrome tests, with no further deletions permitted.
  • Off-by-one in the fallback ranges: deleting the left character means checking (i+1, j), and deleting the right means (i, j-1).