680. Valid Palindrome II - Explanation

Problem Link

Description

You are given a string s, return true if the s can be a palindrome after deleting at most one character from it.

A palindrome is a string that reads the same forward and backward.

Note: Alphanumeric characters consist of letters (A-Z, a-z) and numbers (0-9).

Example 1:

Input: s = "aca"

Output: true

Explanation: "aca" is already a palindrome.

Example 2:

Input: s = "abbadc"

Output: false

Explanation: "abbadc" is not a palindrome and can't be made a palindrome after deleting at most one character.

Example 3:

Input: s = "abbda"

Output: true

Explanation: "We can delete the character 'd'.

Constraints:

  • 1 <= s.length <= 100,000
  • s is made up of only lowercase English letters.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force

Intuition

The simplest approach is to check every possibility. First, check if the string is already a palindrome. If not, try removing each character one at a time and check if the resulting string becomes a palindrome. If any removal produces a palindrome, return true. This guarantees we find a solution if one exists, but it requires checking up to n different strings.

Algorithm

  1. First check if the original string is a palindrome by comparing it to its reverse. If yes, return true.
  2. For each index i from 0 to n-1:
    • Create a new string by removing the character at index i.
    • Check if this new string is a palindrome.
    • If it is, return true.
  3. If no single removal produces a palindrome, return false.
class Solution:
    def validPalindrome(self, s: str) -> bool:
        if s == s[::-1]:
            return True

        for i in range(len(s)):
            newS = s[:i] + s[i + 1:]
            if newS == newS[::-1]:
                return True

        return False

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n)O(n)

2. Two Pointers

Intuition

Instead of blindly trying every removal, we can be smarter. Use two pointers starting from both ends of the string and move them inward. As long as characters match, keep going. When we find a mismatch, we know exactly where the problem is. At this point, we have only two choices: remove the left character or remove the right character. We check if either choice results in a palindrome for the remaining substring.

Algorithm

  1. Initialize two pointers: l at the start and r at the end of the string.
  2. While l < r:
    • If s[l] == s[r], move both pointers inward (l++, r--).
    • If they differ, we found the mismatch. Check two possibilities:
      • Skip the left character and check if s[l+1...r] is a palindrome.
      • Skip the right character and check if s[l...r-1] is a palindrome.
    • Return true if either substring is a palindrome.
  3. If the loop completes without mismatches, the string is already a palindrome. Return true.
class Solution:
    def validPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

        while l < r:
            if s[l] != s[r]:
                skipL = s[l + 1 : r + 1]
                skipR = s[l : r]
                return skipL == skipL[::-1] or skipR == skipR[::-1]
            l, r = l + 1, r - 1

        return True

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Two Pointers (Optimal)

Intuition

The previous two-pointer solution creates new substrings, which costs O(n) space. We can optimize this by passing index bounds to our palindrome check function instead of creating new strings. This way, we check the same characters without allocating extra memory. The logic remains identical: find the first mismatch, then verify if skipping either character leads to a valid palindrome.

Algorithm

  1. Create a helper function isPalindrome(l, r) that checks if s[l...r] is a palindrome using two pointers without creating a new string.
  2. Initialize pointers l = 0 and r = len(s) - 1.
  3. While l < r:
    • If s[l] != s[r], return isPalindrome(l+1, r) or isPalindrome(l, r-1).
    • Otherwise, increment l and decrement r.
  4. Return true if the loop completes (string is already a palindrome).
class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        l, r = 0, len(s) - 1
        while l < r:
            if s[l] != s[r]:
                return (is_palindrome(l + 1, r) or
                        is_palindrome(l, r - 1))
            l += 1
            r -= 1

        return True

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)