Valid Palindrome II

Problem

Given a non-empty string s, you may delete at most one 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: The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Solution

Easy O(n) time O(1) space Solution

public class Solution {
    public boolean validPalindrome(String s) {
        int l = -1, r = s.length();
        while (++l < --r) {
            if (s.charAt(l) != s.charAt(r)) return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
        }
        return true;
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}

Analysis

Since we can only remove one letter, we find the place where we need to remove that one letter
Which is s.charAt(l) != s.charAt(r)
Then we pass l + 1 or r - 1 to see if either of them is palindromic