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

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s consists of lowercase English letters.


class Solution:
    def validPalindrome(self, s: str) -> bool:
        has_deleted = False

        def compare(s, has_deleted):

            if len(s) <= 1:
                return True

            if s[0] == s[-1]:
                return compare(s[1:-1], has_deleted)
            else:
                if not has_deleted:
                    return compare(s[1:], True) or compare(s[:-1], True)
                else:
                    return False

        return compare(s, has_deleted)
class Solution {
    boolean first = false;
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;
        
        
        while(left <= right){
            if( s.charAt(left) == (s.charAt(right))){
                left++;
                right--;
            }else if(!first){
                first = true;
                String removeLeft = s.substring(0,left).concat(s.substring(left+1));
                String removeright = s.substring(0,right).concat(s.substring(right+1));
                left++;
                right--;
                return validPalindrome(removeLeft) || validPalindrome(removeright);   
            } else {
                return false;
            }
        }
     return true;   
    }
}
class Solution {
  int first_diff(string s) {
    for (int i = 0; i < (s.size() + 1) / 2; ++i) {
      if (s[i] != s[s.size() - 1 - i]) {
        return i;
      }
    }
    return -1;
  }
public:
    bool validPalindrome(string s) {
      int diff = first_diff(s);
      if (diff == -1 || (s.size() % 2 == 0 && diff + 1 == s.size() / 2)) {
        // abca. If we have pattern like this than we can delete one of the symbols
        return true;
      }
      
      bool first_valid = true;
      for (int i = diff; i < (s.size() + 1) / 2; ++i) {
        if (s[i] != s[s.size() - 2 - i]) {
          first_valid = false;
          break;
        }
      }
      
      bool second_valid = true;
      for (int i = diff; i < (s.size() + 1) / 2; ++i) {
        if (s[i + 1] != s[s.size() - 1 - i]) {
          second_valid = false;
          break;
        }
      }
      return first_valid || second_valid;
    }
};
/*
Solution:

1. Use two pointers, one initialised to 0 and the other initialised to end of string. Check if characters at each index
are the same. If they are the same, shrink both pointers. Else, we have two possibilities: one that neglects character
at left pointer and the other that neglects character at right pointer. Hence, we check if s[low+1...right] is a palindrome
or s[low...right-1] is a palindrome. If one of them is a palindrome, we know that we can form a palindrome with one deletion and return true. Else, we require more than one deletion, and hence we return false.
*/
var validPalindrome = function(s) {
    let low = 0, high = s.length-1;
    while (low < high) {
        if (s[low] !== s[high]) {
            return isPalindrome(s, low+1, high) || isPalindrome(s, low, high-1);
        }
        low++, high--;
    }
    return true;
    // T.C: O(N)
    // S.C: O(1)
};

function isPalindrome(str, low, high) {
    while (low < high) {
        if (str[low] !== str[high]) return false;
        low++, high--;
    }
    return true;
}
Valid Palindrome II