# Valid Palindrome II
**Difficulty:** EASY
[External](https://leetcode.com/problems/valid-palindrome-ii)
Canonical: https://scaleengineer.com/dsa/problems/valid-palindrome-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [eBay](https://scaleengineer.com/companies/ebay), [Roku](https://scaleengineer.com/companies/roku), [Attentive](https://scaleengineer.com/companies/attentive), [Whatnot](https://scaleengineer.com/companies/whatnot), [Fortinet](https://scaleengineer.com/companies/fortinet)
---
## Problem
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.

# Approaches
## Brute Force by Deleting Each Character
This approach involves systematically trying every possible outcome of deleting a single character from the string. For each character in the string, we remove it, create a new substring, and then check if that new substring is a palindrome. If we find any such palindrome, we can immediately return `true`. This method also needs to account for the case where the string is already a palindrome (zero deletions), which is covered by the 'at most one' deletion rule.
**Time:** O(N^2), where N is the length of the string. The main loop runs N times. Inside the loop, creating a new string by deleting a character takes O(N) time, and checking if the new string is a palindrome also takes O(N) time. This results in a total time complexity of O(N * N) = O(N^2). · **Space:** O(N), where N is the length of the string. In each iteration of the loop, a new string or `StringBuilder` of length N-1 is created, requiring O(N) space.
**Pros:** Conceptually simple and easy to understand.; Straightforward to implement.
**Cons:** Highly inefficient due to O(N^2) time complexity.; Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints (N up to 10^5).
### Explanation
The brute-force method is the most straightforward way to solve the problem. The core idea is to generate all possible strings that can be formed by deleting exactly one character from the original string and test each one for the palindrome property.

We can implement this with a loop that runs from the first to the last character of the string. Inside the loop, for each index `i`, we construct a new string that is a copy of the original but without the character at `i`. Then, we pass this new string to a helper function, `isPalindrome`, which determines if it reads the same forwards and backward.

If the helper function returns `true` at any point, we have found a valid scenario, and our main function can return `true`. If the loop finishes and we haven't found a palindrome, it means deleting one character is not sufficient. We also need to consider the case where zero deletions are needed, i.e., the original string is already a palindrome. A simple way to structure the logic is to first check the original string, and if it's not a palindrome, then proceed with the loop to check for one-deletion palindromes.

```java
class Solution {
    public boolean validPalindrome(String s) {
        // Case for 0 deletions
        if (isPalindrome(s, 0, s.length() - 1)) {
            return true;
        }

        // Case for 1 deletion
        for (int i = 0; i < s.length(); i++) {
            // Create a new string by deleting the character at index i
            StringBuilder sb = new StringBuilder(s);
            sb.deleteCharAt(i);
            if (isPalindrome(sb.toString(), 0, sb.length() - 1)) {
                return true;
            }
        }
        
        return false;
    }

    private boolean isPalindrome(String str, int left, int right) {
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- First, handle the base case of 0 deletions by checking if the original string `s` is a palindrome. If it is, return `true`.
- Iterate through the string `s` with an index `i` from `0` to `s.length() - 1`.
- In each iteration, create a temporary string by deleting the character at index `i`. A `StringBuilder` is efficient for this.
- Check if the resulting temporary string is a palindrome using a helper function.
- If the temporary string is a palindrome, it means we can form a palindrome by deleting one character, so return `true`.
- If the loop completes without finding any such case, it means deleting one character does not help. Return `false`.

## Greedy Two-Pointer Approach
This is an efficient approach that uses two pointers to scan the string from both ends. We move the pointers inward as long as the characters match. When we find a mismatch, we know that one of the two mismatched characters must be the one to be deleted. This gives us two possibilities to check: the substring without the left character, or the substring without the right character. If either of these substrings forms a palindrome, then the original string satisfies the condition.
**Time:** O(N), where N is the length of the string. The main `while` loop runs at most N/2 times. If a mismatch is found, we call `isPalindrome` on a substring. In the worst case, this involves checking the rest of the string. However, this check happens at most once. The total number of character comparisons is linear with respect to N. · **Space:** O(1). We only use a few variables to store pointers and indices, which consumes constant extra space regardless of the input string size.
**Pros:** Optimal time complexity of O(N).; Efficient space complexity of O(1).; Handles all cases (0 or 1 deletion) gracefully in a single pass.
**Cons:** Slightly more complex to reason about than the brute-force approach.
### Explanation
The two-pointer approach provides a significant performance improvement. We set up two pointers, `left` at the start of the string and `right` at the end.

We advance the pointers towards each other, comparing characters at each step. As long as `s.charAt(left)` equals `s.charAt(right)`, the substring between them could be part of a palindrome, so we continue by incrementing `left` and decrementing `right`.

The crucial part is when we encounter the first mismatch, i.e., `s.charAt(left) != s.charAt(right)`. At this point, the string can only become a palindrome if we remove one of these two characters. This leads to two scenarios:
1. We delete the character at the `left` pointer and check if the remaining substring from `left + 1` to `right` is a palindrome.
2. We delete the character at the `right` pointer and check if the remaining substring from `left` to `right - 1` is a palindrome.

If either of these checks passes, we have found a solution, and we can return `true`. If both fail, then it's impossible to make the string a palindrome by deleting just one character, so we return `false`. A helper function `isPalindrome(s, start, end)` is perfect for checking these subproblems.

If the main `while` loop finishes without ever finding a mismatch, it means the original string is already a palindrome, which satisfies the 'at most one deletion' condition, so we return `true`.

```java
class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                // Found a mismatch, try deleting one character from either end.
                return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
            }
            left++;
            right--;
        }
        
        // If the loop completes, the string is already a palindrome.
        return true;
    }

    // Helper function to check if a substring is a palindrome.
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize two pointers: `left = 0` and `right = s.length() - 1`.
- Loop as long as `left < right`.
- Compare the characters at the `left` and `right` pointers.
- If `s.charAt(left)` is the same as `s.charAt(right)`, they form a valid pair, so move the pointers inward: `left++`, `right--`.
- If `s.charAt(left)` is not equal to `s.charAt(right)`, this is a mismatch. This is our one chance to delete a character. We have two possibilities:
  1. The character at `left` is the problem. We check if the substring `s[left+1...right]` is a palindrome.
  2. The character at `right` is the problem. We check if the substring `s[left...right-1]` is a palindrome.
- We use a helper function to check these two sub-cases. If either of them returns `true`, the overall condition is met, and we return `true`.
- If both sub-cases return `false`, it's impossible to make a palindrome by deleting one character, so we return `false`.
- If the main loop completes without any mismatches, the string was already a palindrome, so we return `true`.

# Solutions
### JavaScript

```javascript
/** * @param {string} s * @return {boolean} */ var validPalindrome = function (
  s,
) {
  let check = function (i, j) {
    for (; i < j; ++i, --j) {
      if (s.charAt(i) != s.charAt(j)) {
        return false;
      }
    }
    return true;
  };
  for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
    if (s.charAt(i) != s.charAt(j)) {
      return check(i + 1, j) || check(i, j - 1);
    }
  }
  return true;
};

```

### CSharp

```csharp
public class Solution {
    public bool ValidPalindrome(string s) {
        int i = 0, j = s.Length - 1;
        while (i < j && s[i] == s[j]) {
            i++;
            j--;
        }
        if (i >= j) {
            return true;
        }
        return check(s, i + 1, j) || check(s, i, j - 1);
    }
    private bool check(string s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}
```

### Java

```java
class Solution {
public
  boolean validPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
      if (s.charAt(i) != s.charAt(j)) {
        return check(s, i + 1, j) || check(s, i, j - 1);
      }
    }
    return true;
  }
private
  boolean check(String s, int i, int j) {
    for (; i < j; ++i, --j) {
      if (s.charAt(i) != s.charAt(j)) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution { public: bool validPalindrome ( string s ) { for ( int i = 0 , j = s . size () - 1 ; i < j ; ++ i , -- j ) { if ( s [ i ] != s [ j ]) { return check ( s , i + 1 , j ) || check ( s , i , j - 1 ); } } return 1 ; } bool check ( string s , int i , int j ) { for (; i < j ; ++ i , -- j ) { if ( s [ i ] != s [ j ]) { return false ; } } return true ; } };
```

### Python

```python
class Solution : def validPalindrome ( self , s : str ) -> bool : def check ( i , j ): while i < j : if s [ i ] != s [ j ]: return False i , j = i + 1 , j - 1 return True i , j = 0 , len ( s ) - 1 while i < j : if s [ i ] != s [ j ]: return check ( i , j - 1 ) or check ( i + 1 , j ) i , j = i + 1 , j - 1 return True
```