Algorithm to Delete a Character to Make a Valid Palindrome

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.

Intuitive Bruteforce Algorithm

Let’s try to delete one character and see if it makes a valid palindrome string. We can define a validPalindrome function that takes an additional parameter index, which will be the target index to delete.

By passing -1, we are assuming no character will be deleted. The function runs at O(N) complexity and the ovarall time complexity is O(N^2). A few notes on the implementation:

• the string should be passed by reference, otherwise a copy will be made, which will be memory-inefficient.
• we can use the string.substring() to concate the two substring – which virtually delete a character.
• The size() function is unsigned, thus we need to convert it to int or use size_t to declare the loop variable i. However, as -1 is negative, we need to convert the size() to signed integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool validPalindrome(string s) {
        for (int i = -1; i < (int)s.size(); i ++) {
            if (validPalindrome(s, i)) {
                return true;
            }
        }
        return false;
    }
    
private:
    bool validPalindrome(const string &s, int idx) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            if (i == idx) i ++;
            if (j == idx) j --;
            if (s[i] != s[j]) return false;
            i ++;            
            j --;            
        }
        return true;
    }
};

class Solution {
public:
    bool validPalindrome(string s) {
        for (int i = -1; i < (int)s.size(); i ++) {
            if (validPalindrome(s, i)) {
                return true;
            }
        }
        return false;
    }
    
private:
    bool validPalindrome(const string &s, int idx) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            if (i == idx) i ++;
            if (j == idx) j --;
            if (s[i] != s[j]) return false;
            i ++;            
            j --;            
        }
        return true;
    }
};

The above C++ implementation is apparently not fast enough.

Greedy algorithm to Delete a Character to Make a Valid Palindrome

We first need to define a palindrome function takes takes additional two indice as a range. This function will check if the range i.e. s.substring(from, to-from+1) forms a valid palindrome. This takes O(N) time.

Then, we need to do the normal palindrome check until we have a mismatch, let’s say, s[i] != s[j], at this point, in order to make a valid palindrome by removing a character, there are two possibilities, either s[i:j-1] is a palindrome or s[i+1:j] is.

The entire algorithm runs at O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    bool validPalindrome(string s) {
        for (int i = 0; i < s.size() / 2; i ++) {
            int j = s.size() - 1 - i;
            if (s[i] != s[j]) {
                return validPalindrome(s, i, j - 1) ||
                    validPalindrome(s, i + 1, j);
            }
        }
        return true;
    }
    
private:
    bool validPalindrome(const string &s, int from, int to) {
        int i = from, j = to;
        while (i < j) {
            if (s[i] != s[j]) return false;
            i ++;            
            j --;            
        }
        return true;
    }
};

class Solution {
public:
    bool validPalindrome(string s) {
        for (int i = 0; i < s.size() / 2; i ++) {
            int j = s.size() - 1 - i;
            if (s[i] != s[j]) {
                return validPalindrome(s, i, j - 1) ||
                    validPalindrome(s, i + 1, j);
            }
        }
        return true;
    }
    
private:
    bool validPalindrome(const string &s, int from, int to) {
        int i = from, j = to;
        while (i < j) {
            if (s[i] != s[j]) return false;
            i ++;            
            j --;            
        }
        return true;
    }
};

Both valid palindrome implementations take constant space complexity.

–EOF (The Ultimate Computing & Technology Blog) —