680

680. Valid Palindrome II (Easy)

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

 

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

 

Constraints:

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

Companies:
Facebook, Amazon, Microsoft, Bloomberg

Related Topics:
Two Pointers, String, Greedy

Similar Questions:

• Valid Palindrome (Easy)
• Valid Palindrome III (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/valid-palindrome-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool validPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        while (i < j && s[i] == s[j]) ++i, --j;
        if (i >= j) return true;
        auto valid = [&](int i, int j) {
            while (i < j && s[i] == s[j]) ++i, --j;
            return i >= j;
        };
        return valid(i + 1, j) || valid(i, j - 1);
    }
};