Valid Palindrome II

680.Valid Palindrome II

String

Two Pointers

Greedy

Problem Statement:

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

Example:

Input:

s = "abca"

→

Output:

true

Algorithm:

1. Use two pointers from ends
2. When mismatch found, try skipping either character
3. Check if remaining substring is palindrome
4. Only need to check one deletion

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public boolean validPalindrome(String s) {
    int i = 0;
    int j = s.length() - 1;

    while (i < j) {
        if (s.charAt(i) != s.charAt(j))  // Found mismatch
            return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);  // Try both deletions
        i++; j--;  // Remember to decrement these after!!
    }
    return true;
}

public boolean isPalindrome(String s, int i, int j) {
    while (i < j) 
        if (s.charAt(i++) != s.charAt(j--))
            return false;
    return true;
}

Python Solution:

def validPalindrome(self, s: str) -> bool:
    def isPalindrome(left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:  # Try both deletions
            return isPalindrome(left + 1, right) or isPalindrome(left, right - 1)
        left += 1
        right -= 1
    return True

C++ Solution:

class Solution {
private:
    bool isPalindrome(string& s, int i, int j) {
        while(i < j) {
            if(s[i++] != s[j--]) return false;
        }
        return true;
    }
    
public:
    bool validPalindrome(string s) {
        int i = 0, j = s.length() - 1;
        
        while(i < j) {
            if(s[i] != s[j]) {  // Try both possible deletions
                return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
            }
            i++; j--;
        }
        return true;
    }
};