Valid Palindrome II Leetcode Solution

Problem Statement

The Valid Palindrome II LeetCode Solution – “Valid Palindrome II” states that given the string s, we need to return true if s can be a palindrome string after deleting at most one character.

Example:

Input:  s = "aba"

Output: true

Explanation:

• The input string is already palindrome, so there’s no need to delete any character.

Input:  "abc"

Output: false

Explanation:

• We cannot have a palindrome string after deleting at most one character.
• Strings formed after deleting 1 character are: [“bc”, “ac”, “ab”]. None of them are palindromes.

Approach

Idea:

1. The main idea to solve this problem is to use Palindrome Checking, from the start and back sides of the input string.
2. Initialize l = 0, and r = n – 1, where n = length of the string.
3. Iterate till characters s[l] and s[r] are equal while, l must be less than or equal to r.
4. Now, whenever, characters at the lth and rth position are unequal, we need to delete either the lth character or rth character of the input string.
5. So, there are two cases:
   1. If the input string is already a palindrome string otherwise,
   2. If S(l,r-1) is a palindrome string or S(l+1,r) is a palindrome string.
6. Note that l and r are the indexes where characters differ.
7. Return true, of any of the cases are true in 5, otherwise false.

Code

Valid Palindrome II C++ Solution:

class Solution {
public:
    bool isPal(int l,int r,string s){
        while(l<r){
            if(s[l]!=s[r]){
                return false;
            }
            l++;r--;
        }
        return true;
    }
    bool validPalindrome(string s) {
        int l = 0,r = s.length() - 1;
        while(l<r and s[l]==s[r]){
            l++;r--;
        }
        return isPal(l+1,r,s) or isPal(l,r-1,s);
    }
};

Valid Palindrome II Java Solution:

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

Complexity Analysis for Valid Palindrome II Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since we access every character at most twice.

Space Complexity

The space complexity of the above code is O(1) since we’re using constant space.