Solution For Valid Palindrome Ii

Problem Statement:

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:

The problem can be solved using two pointers approach. We can start comparing characters from start and end at the same time, and if we find any mismatch, we can try deleting any of those characters from one end and check if remaining string is a palindrome or not. If it is a palindrome, then the given string can be made a palindrome by deleting only one character.

1. Initialize two pointers, i and j, pointing to the start and end of the string respectively.
2. Iterate the string while i is less than or equal to j. If a mismatch is found, then we can either delete character at i or j and try to check if the remaining string is palindrome or not. At this point, we can use a recursive call to check if removing any of these characters from either end makes the remaining string a palindrome or not.
3. If the string is a palindrome, then return True.
4. If we have tried all possibilities of removing one character and still not able to find a palindrome, then return False.

Code:

class Solution:
def validPalindrome(self, s: str) -> bool:
i, j = 0, len(s) – 1
while i <= j:
if s[i] == s[j]:
i += 1
j -= 1
else:
return self.isPalindrome(s, i+1, j) or self.isPalindrome(s, i, j-1)
return True

def isPalindrome(self, s: str, i: int, j: int) -> bool:
    while i <= j:
        if s[i] == s[j]:
            i += 1
            j -= 1
        else:
            return False
    return True

Explanation:

In our solution, we first initialize pointers i and j to point to first and last character of the string s. We then start iterating over the string comparing the characters at the two ends. If we find a mismatch, we can try removing either character and check if the remaining string is a palindrome or not.

The “isPalindrome” function is a helper function that checks if the given substring is a palindrome or not. It takes a string s and two pointers i and j as inputs, and then checks if the substring from i to j is a palindrome by comparing the characters at the two ends of the string. If it finds a mismatch, it returns False, otherwise it returns True.

The “validPalindrome” function implements the main logic of our program. It first initializes pointers i and j to point to the first and last character of the string respectively. It then starts iterating over the string checking the characters at both ends. If it finds a mismatch, it tries to remove either of two characters – one pointed by i and the other pointed by j – and checks if the remaining string is a palindrome or not. If it finds a palindrome, it returns True, otherwise it continues to the next iteration. If it has tried all possibilities of removing one character and still not able to find a palindrome, it returns False.

The time complexity of our solution is O(n), where n is length of the input string, as we need to iterate over the entire string only once. The space complexity is O(1), as we are not using any extra memory for storing the string or any other data.

Step by Step Implementation For Valid Palindrome Ii

public boolean validPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) {
            return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
        }
        i++;
        j--;
    }
    return true;
}

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

def validPalindrome(self, s: str) -> bool:
        # two pointers
        # if encounter a mismatch, check if the remaining string is a palindrome
        # or if the string without the current character is a palindrome
        
        left = 0
        right = len(s) - 1
        
        while left < right:
            if s[left] != s[right]:
                return self.isPalindrome(s, left+1, right) or self.isPalindrome(s, left, right-1)
            else:
                left += 1
                right -= 1
                
        return True
    
    def isPalindrome(self, s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            else:
                left += 1
                right -= 1
                
        return True

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
    // Two pointer approach
    // Start from the beginning and the end of the string
    // If the characters at the pointers match, move the pointers inwards
    // If the characters do not match, check if the string is a palindrome
    // if removing one character from the string makes it a palindrome
    // return true, otherwise return false
    
    let left = 0;
    let right = s.length - 1;
    
    while (left < right) {
        if (s[left] !== s[right]) {
            return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
        }
        left++;
        right--;
    }
    
    return true;
};

var isPalindrome = function(s, left, right) {
    // Helper function to check if a string is a palindrome
    // Start from the beginning and the end of the string
    // If the characters at the pointers match, move the pointers inwards
    // If the characters do not match at any point, return false
    // Otherwise return true
    
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
};

class Solution {
public:
    bool validPalindrome(string s) {
        int n = s.length();
        int i = 0, j = n-1;
        while(i < j){
            if(s[i] != s[j]){
                return isValid(s, i+1, j) || isValid(s, i, j-1);
            }
            i++;
            j--;
        }
        return true;
    }
    
    bool isValid(string s, int i, int j){
        while(i < j){
            if(s[i] != s[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
};

public class Solution {
    public bool ValidPalindrome(string s) {
        //We will use two pointers to iterate through the string
        //One pointer will start from the beginning of the string and the other will start from the end
        //We will compare the characters at each index of the string
        //If there is a mismatch, we will check if the string is a palindrome if we omit that character
        int left = 0;
        int right = s.Length - 1;
        
        while(left < right) {
            if(s[left] != s[right]) {
                //The string is not a palindrome if omitting the character at index left does not result in a palindrome
                if(!IsPalindrome(s, left + 1, right)) {
                    return false;
                }
                //The string is not a palindrome if omitting the character at index right does not result in a palindrome
                if(!IsPalindrome(s, left, right - 1)) {
                    return false;
                }
            }
            //Increment left and decrement right
            left++;
            right--;
        }
        return true;
    }
    
    //This function returns true if the string is a palindrome when omitting the character at index i
    public bool IsPalindrome(string s, int i, int j) {
        while(i < j) {
            if(s[i] != s[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}