Given a non-empty strings, you may deleteat mostone character. Judge whether you can make it a palindrome.

Example 1:

Input:
 "aba"

Output:
 True

Example 2:

Input:
 "abca"

Output:
 True

Explanation:
 You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

class Solution {
    public boolean validPalindrome(String s) {
        for (int i = 0; i < s.length() / 2; i++){
            int j = s.length() - i - 1;
            if (s.charAt(i) != s.charAt(j)) return isValid(s.substring(i + 1, j + 1)) || isValid(s.substring(i, j));
        }

        return true;
    }

    private boolean isValid(String s){
        int left = 0, right = s.length() - 1;
        while (left < right){
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }

        return true;
    }
}