## Algorithm

Problem Name: 680. Valid Palindrome II

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.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool validPalindrome(string s) {
int i = 0, j = s.size() - 1;
while(i  < = j && s[i] == s[j]) i++, j--;
return i > j || isValid(s.substr(i, j - i)) || isValid(s.substr(i + 1, j - i));
}

bool isValid(string s){
int i = 0, j = s.size() - 1;
while(i  < = j && s[i] == s[j]) i++, j--;
return i > j;
}
};
``````
Copy The Code &

Input

cmd
s = "aba"

Output

cmd
true

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean validPalindrome(String s) {
return validPalindromeHelper(s, false);
}

private boolean validPalindromeHelper(String s, boolean deleted) {
int startIdx = 0;
int endIdx = s.length() - 1;
while (startIdx  <  endIdx) {
if (s.charAt(startIdx) != s.charAt(endIdx)) {
if (deleted) {
return false;
}
return validPalindromeHelper(s.substring(0, startIdx) + s.substring(startIdx + 1), true) ||
validPalindromeHelper(s.substring(0, endIdx) + s.substring(endIdx + 1), true);
}
startIdx++;
endIdx--;
}
return true;
}
}
``````
Copy The Code &

Input

cmd
s = "aba"

Output

cmd
true

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const validPalindrome = function(s) {
let start = 0;
let end = s.length - 1;

const isPalindrome = function(start, end, removed) {
while (start  < = end) {
if (s[start] !== s[end]) {
if (removed) {
return false;
}

return (
isPalindrome(start + 1, end, true) ||
isPalindrome(start, end - 1, true)
);
}
start++;
end--;
}
return true;
};

return isPalindrome(start, end, false);
};
``````
Copy The Code &

Input

cmd
s = "abca"

Output

cmd
true

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
memo = {}
def dfs(l, r, cnt):
if (l, r, cnt) in memo:
return memo[(l, r, cnt)]
if l >= r:
return True
elif s[l] != s[r]:
cnt += 1
if cnt > 1:
memo[(l, r, cnt)] = False
return False
elif (s[l + 1] == s[r] and dfs(l + 1, r, cnt + 1)) or (s[l] == s[r - 1] and dfs(l, r - 1, cnt + 1)):
memo[(l, r, cnt)] = True
return True
else:
memo[(l, r, cnt)] = False
return False
else:
memo[(l, r, cnt)] = dfs(l + 1, r - 1, cnt)
return memo[(l, r, cnt)]
return dfs(0, len(s) - 1, 0)
``````
Copy The Code &

Input

cmd
s = "abca"

Output

cmd
true

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0680_ValidPalindromeII
{
public bool ValidPalindrome(string s)
{
for (int i = 0; i  <  s.Length / 2; i++)
{
var j = s.Length - 1 - i;
if (s[i] != s[j])
return ValidPalindrome(s, i, j - 1) || ValidPalindrome(s, i + 1, j);
}

return true;
}

private bool ValidPalindrome(string s, int i, int j)
{
for (int k = i; k  < = i + (j - i) / 2; k++)
if (s[k] != s[j - k + i]) return false;

return true;
}
}
}
``````
Copy The Code &

Input

cmd
s = "abc"

Output

cmd
false