680. Valid Palindrome II

Greedy, Two Pointers, String, AMateList · 15 Aug 2024

Problem Statement

link: LeetCode.cn LeetCode Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example:

Input: s = "aba" Output: true

Input: s = "abca" Output: true

Input: s = "abc" Output: false

Constraints: 1 <= s.length <= 105 s consists of lowercase English letters.

Solution Approach

Use a two-pointer approach to check for mismatches, and if found, verify if removing one character can result in a palindrome.

Algorithm

Use two pointers to compare characters from the start and end of the string.
If a mismatch occurs, check if removing one character from either end can result in a palindrome.
Return true if either modified substring is a palindrome; otherwise, return false.

Implement

    class Solution:
    def validPalindrome(self, s: str) -> bool:
        def checkPalindrome(low, high):
            i, j = low, high
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True
        
        low, high = 0, len(s) - 1
        while low < high:
            if s[low] == s[high]:
                low += 1
                high -= 1
            else:
                return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)
        return True