package string;

/**
 * Created by gouthamvidyapradhan on 09/12/2017.
 * 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.
 */
public class ValidPalindromeII {

    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        System.out.println(new ValidPalindromeII().validPalindrome("aaaaaab"));
    }

    public boolean validPalindrome(String s) {
        for(int i = 0, j = s.length() - 1; i < j;){
            if(s.charAt(i) == s.charAt(j)){
                i++; j--;
            } else {
                return isPaliandrome(s.substring(i, j)) || isPaliandrome(s.substring(i + 1, j + 1));
            }
        }
        return true;
    }

    private boolean isPaliandrome(String s){
        for(int i = 0, j = s.length() - 1; i < j;){
            if(s.charAt(i) == s.charAt(j)){
                i++; j--;
            } else return false;
        }
        return true;
    }
}