Leetcode 680. Valid Palindrome II

Problem Explanation

The problem is a variant of a classical string problem i.e. to check if a given string is a palindrome or not. The only twist here is that we are allowed to delete at most one character. This operation can be performed either not at all or exactly once.

A palindrome is a word that is the same forward as backwards, ignoring spaces. So, for example, the words "race car" and "deed" are palindromes.

The function validPalindrome(s) takes in a string s as an argument and returns a boolean value (i.e., true if you can make the string a palindrome by deleting at most one character, or false if this is impossible).

A key constraint to our problem is that our string will only contain lowercase characters from 'a' to 'z'.

Walkthrough Example

Consider the input string "abca".

We iterate from both ends of the string. We can see that the string fails palindrome check at characters b and c. Now we are allowed to delete at most one character. There are two options either delete 'b' or delete 'c'. If we delete 'b' the resultant string is "aca" which is not a palindrome. But if we delete 'c' the resultant string is "aba" which is a palindrome. So the output in this case will be True.

Approach to the Solution

In the problem statement, if we consider the case where we are allowed to delete only one character. We can start checking our string 's' from both ends. If at any point of time, the character at our left pointer is not equal to the character at right pointer, we can try deleting one character at either of the pointers and check if the remaining string can form a palindrome or not.

Python Solution

1
2python
3class Solution:
4    def validPalindrome(self, s: str) -> bool:
5        # Inner function to check if string is palindrome when characters at indexes [l, r] are deleted
6        def is_pali_range(s, l, r):
7            return all(s[i] == s[r-i+l] for i in range(l, r))
8        
9        # Start and end pointers
10        for i in range(len(s) // 2):  
11            if s[i] != s[~i]:
12                j = len(s) - 1 - i
13                return is_pali_range(s, i+1, j) or is_pali_range(s, i, j-1)
14        return True

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool validPalindrome(string s) {
6        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
7            if (s[i] != s[j]) {
8                int i1 = i, j1 = j - 1, i2 = i + 1, j2 = j;
9                while (i1 < j1 && s[i1] == s[j1]) {i1++; j1--;}
10                while (i2 < j2 && s[i2] == s[j2]) {i2++; j2--;}
11                return i1 >= j1 || i2 >= j2;
12            }
13        }
14        return true;
15    }
16};
17

Java Solution

1
2java
3class Solution {
4    public boolean validPalindrome(String s) {
5        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
6            if (s.charAt(i) != s.charAt(j)) {
7                return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
8            }
9        }
10        return true;
11    }
12
13    private boolean isPalindrome(String s, int i, int j) {
14        for (; i < j; i++, j--) {
15            if (s.charAt(i) != s.charAt(j)) {
16                return false;
17            }
18        }
19        return true;
20    }
21}

JavaScript Solution

1
2JavaScript
3/**
4 * @param {string} s
5 * @return {boolean}
6 */
7const validPalindrome = function(s) {
8    let l = 0, r = s.length - 1;  
9    while(l < r) {
10        if(s[l] !== s[r]) 
11            return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
12        l++; 
13        r--;
14    }
15    return true;
16};
17
18const isPalindrome = function(s, l, r) {
19    while(l < r) {
20        if(s[l++] !== s[r--]) 
21            return false;
22    }
23    return true;
24};

Here, we are using a two pointer approach (just like in other solutions). We keep two pointers, one at the beginning of the string l and the other at the end r. We iterate over the string, checking the characters at index l and r, if they are not the same, we consider removing either of the characters and then check if the remaining string is a palindrome or not. We have an additional helper function to perform the palindrome check isPalindrome(s, l, r).

Time Complexity Analysis

The time complexity of the problem is O(n) where n is the length of the string s because in the worst case, we iterate the string s once. In Python we use the all() function which checks for every value inside a generator which in worst case can cost us n/2 operations where ~i == -i-1 which is basically reverting i. For JavaScript, Java, and C++, we increment and decrement pointers until they meet in the middle, carrying out n/2 operations. Thus, we keep the computational complexity linear in all cases. The space complexity of the problem is O(1), because no extra space is used. It's important to note that we aren't actually creating new copies of the string during the process, instead we are just creating new pointers (or references) to the existing string.