680 Valid Palindrome II

Techniques Used

• Two Pointer

Difficulty

• Easy

Approach

• Have start and end variables which will help us traverse the string s.
• In the while loop,
  • If the start and end character are not equal at some point, we additionally will need to check whether substring from start + 1 to end OR substring from start to end -1 are palindromes.
  • If either of them are palindromes, we will return true in this case, else false.
  • If the start and end character are same, no need to do anything apart from incrementing start, and decrementing end.
• return true because if there was any change of returning false, it would have already been returned. Since it didn't, we should return true since there was requirement of deleting 1 character to make it a palindrome.

Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

Code: Java

class Solution {
    public boolean validPalindrome(String s) {

        if(s.length() == 1) return true;

        int start = 0;
        int end = s.length() - 1;

        while(start < end){

            if(s.charAt(start) != s.charAt(end)){
                return isPalindrome(s, start + 1, end) || isPalindrome(s, start, end - 1);
            }

            start++;
            end--;

        }

        return true;
    }

    static boolean isPalindrome(String s, int start, int end){

        if(start > end) return false;

        while(start < end){
            if(s.charAt(start) != s.charAt(end)) return false;

            start++;
            end--;
        }

        return true;


    }
}

Code: C++

class Solution {
public:
    bool validPalindrome(string s) {

        if(s.size() == 1) return true;

        int start = 0;
        int end = s.size() - 1;

        while(start < end){

            if(s[start] != s[end]){
                return isPalindrome(s, start + 1, end) || isPalindrome(s, start, end - 1);
            }

            start++;
            end--;

        }

        return true;
    }

   bool isPalindrome(string s, int start, int end){

        if(start > end) return false;

        while(start < end){
            if(s[start] != s[end]) return false;

            start++;
            end--;
        }

        return true;


    }
};