Valid Palindrome Ii - Leetcode Solution

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.

1