680. Valid Palindrome II

Problem

Tags: Two Pointers, String, Greedy

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

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

Code

C

// 680. Valid Palindrome II (12/19/54221)
// Runtime: 12 ms (90.89%) Memory: 9.10 MB (39.80%) 

bool is_palindrome(char* s, int n) {
    int half = n / 2;
    
    for (int i = 0; i < half; i++) {
        if (s[i] != s[n - 1 - i]) {
            return false;
        }
    }
    
    return true;
}

bool validPalindrome (char* s) {
    int len = strlen(s);
    bool used = false;
    int left = 0, right = len - 1;
    
    while (left < right) {
        if (s[left] != s[right]) {
            if (used) {
                return false;
            }
            
            if (s[left] == s[right - 1] || s[left + 1] == s[right]) {
                return is_palindrome(s + left, right - left) || is_palindrome(s + left + 1, right - left);
            }
            else {
                return false;
            }
            
            used = true;
        }
        
        left++;
        right--;
    }
    
    return true;
}