Valid Palindrome II

Difficulty: Easy | Acceptance: 44.20% | Paid: No Topics: Two Pointers, String, Greedy

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

• Examples
• Constraints
• Brute Force
• Two Pointers

Examples

Example 1

Input: s = "aba"
Output: true
Explanation: Already a palindrome.

Example 2

Input: s = "abca"
Output: true
Explanation: Delete 'b' or 'c'.

Example 3

Input: s = "abc"
Output: false

Constraints

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Brute Force

Intuition We can try deleting every character from the string one by one and check if the resulting string is a palindrome. If the original string is already a palindrome, we return true immediately.

Steps

• Check if the string s is already a palindrome. If yes, return true.
• Iterate through each index i of the string.
• Create a new string by skipping the character at index i.
• Check if this new string is a palindrome.
• If any of these new strings is a palindrome, return true.
• If the loop finishes without finding a valid palindrome, return false.

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(t):
            return t == t[::-1]
        
        if is_palindrome(s):
            return True
        
        for i in range(len(s)):
            if is_palindrome(s[:i] + s[i+1:]):
                return True
                
        return False

Complexity

• Time: O(n²) - Creating a substring takes O(n) and we do it for n characters.
• Space: O(n) - To store the temporary substring.
• Notes: Simple to implement but inefficient for large strings.

Two Pointers

Intuition Use two pointers starting at both ends of the string. If characters match, move pointers inward. If a mismatch occurs, we have exactly one chance to delete a character. We check if the string becomes a palindrome by skipping either the left character or the right character.

Steps

• Initialize left pointer to 0 and right pointer to s.length - 1.
• While left < right:
  • If s[left] == s[right], increment left and decrement right.
  • If s[left] != s[right]:
    • Check if the substring s[left+1...right] is a palindrome.
    • OR check if the substring s[left...right-1] is a palindrome.
    • Return the result of these checks.
• If the loop completes without returning false, it means the string is a palindrome (or became one by matching all pairs), so return true.

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(s, 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(s, l + 1, r) or is_palindrome(s, l, r - 1)
            l += 1
            r -= 1
        return True

Complexity

• Time: O(n) - We traverse the string at most twice.
• Space: O(1) - No extra space proportional to input size is used.
• Notes: Optimal solution for this problem.