Valid Palindrome II

Problem

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Constraints

• 1 <= s.length <= 105
• s consists of lowercase English letters.

Solution

The problem Valid Palindrome II can be solved by comparing letters starting from each side. When every characters are identical, then the given string is a palindrome without having to delete any characters. When characters at left and right index are different, restart the process but this time using a substring s[left+1:right] and a substring s[left:right-1]. If all characters in any one of the substrings are identical, then the given string can be a palindrome after deleting a single character.

Implementation

class Solution
{
  public:
    bool helper(string s, int left, int right)
    {
        while (left < right)
            if (s[left++] != s[right--])
                return false;

        return true;
    }

    bool validPalindrome(string s)
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        int left = 0, right = s.length() - 1;

        while (left < right)
            if (s[left++] != s[right--])
                return helper(s, left - 1, right) || helper(s, left, right + 1);

        return true;
    }
};