Valid Palindrome II Problem


Description

LeetCode Problem 680.

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

Example 1:

1
2
Input: s = "aba"
Output: true

Example 2:

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

Example 3:

1
2
Input: s = "abc"
Output: false

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool validPalindrome(string s) {
        int lo = 0, hi = s.size() - 1;
        return validPalindrome(s, lo, hi, 0);
    }
    
    bool validPalindrome(string& s, int lo, int hi, int count) {
        if (count > 1) return false;
        while (lo < hi) {
            if (s[lo] == s[hi]) {
                lo++; hi--;
            } else {
                return validPalindrome(s, lo + 1, hi, count + 1) || 
                        validPalindrome(s, lo, hi - 1, count + 1);
            }
        }
        return true;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...