Problem description:

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:

Can delete at most one character, implies that the string will not be valid if we delete one character and it does not make a valid palindrome.

  1. Design a subfunction to check the string is valid or not.
  2. When we encounter two different characters, we can choose to delete one of them, and check if it’s valid or not.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def validPalindrome(self, s: str) -> bool:
        def isPalin(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                else:
                    l += 1
                    r -= 1
            return True
        i, j = 0, len(s)-1
        while i < j:
            if s[i] != s[j]:
                return isPalin(i+1, j) or isPalin(i, j-1)
            i += 1
            j -= 1
            
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool validPalindrome(string s) {
        int l= 0, r= s.length()-1;
        while(l< r){
            if(s[l] != s[r])
                return isValid(s, l+1, r) || isValid(s, l, r-1);
            l++; r--;
        }
        return true;
    }
    
    bool isValid(string s, int left, int right){
        while(left< right){
            if(s[left] != s[right])
                return false;
            left++; right--;
        }
        return true;
    }
};

Solution:

Similar idea as above

  1. remove the character if s[i] and s[j] are different
  2. compare the two strings with their reversed string. Note that we only need to compare the rest of string.
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def validPalindrome(self, s: str) -> bool:
        i, j = 0, len(s)-1
        while i < j:
            if s[i] != s[j]:
                one = s[i:j] # remove s[j]
                two = s[i+1:j+1] # remove s[i]
                return one == one[::-1] or two == two[::-1]
            else:
                i += 1
                j -= 1
        return True

time complexity: $O(n)$

reference: